English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Interval graphs, intersection graphs of segments on a real line (intervals),play a key role in the study of algorithms and special structural properties.Unit interval graphs, their proper subclass, where each interval has a unitlength, has also been extensively studied. We study mixed unit intervalgraphs---a generalization of unit interval graphs where each interval has stilla unit length, but intervals of more than one type (open, closed, semi-closed)are allowed. This small modification captures a much richer class of graphs. Inparticular, mixed unit interval graphs are not claw-free, compared to unitinterval graphs.  Heggernes, Meister, and Papadopoulos defined a representation of unitinterval graphs called the bubble model which turned out to be useful inalgorithm design. We extend this model to the class of mixed unit intervalgraphs and demonstrate the advantages of this generalized model by providing asubexponential-time algorithm for solving the MaxCut problem on mixed unitinterval graphs. In addition, we derive a polynomial-time algorithm for certainsubclasses of mixed unit interval graphs. We point out a substantial mistake inthe proof of the polynomiality of the MaxCut problem on unit interval graphs byBoyaci, Ekim, and Shalom (2017). Hence, the time complexity of this problem onunit interval graphs remains open. We further provide a better algorithmicupper-bound on the clique-width of mixed unit interval graphs. Clique-width isone of the most general structural graph parameters, where a large group ofnatural problems is still solvable in the tractable time when an efficientrepresentation is given. Unfortunately, the exact computation of theclique-width representation is \NP-hard. Therefore, good upper-bounds onclique-width are highly appreciated, in particular, when such a bound isalgorithmic.

U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited