U-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10420244" target="_blank" >RIV/00216208:11320/20:10420244 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4230/LIPIcs.MFCS.2020.57" target="_blank" >https://doi.org/10.4230/LIPIcs.MFCS.2020.57</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2020.57" target="_blank" >10.4230/LIPIcs.MFCS.2020.57</a>
Alternative languages
Result language
angličtina
Original language name
U-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited
Original language description
Heggernes, Meister, and Papadopoulos defined a representation of unit interval graphs called the bubble model which turned out to be useful in algorithm design. We extend this model to the class of mixed unit interval graphs and demonstrate the advantages of this generalized model by providing a subexponential-time algorithm for solving the MaxCut problem on mixed unit interval graphs. In addition, we derive a polynomial-time algorithm for certain subclasses of mixed unit interval graphs. We point out a substantial mistake in the proof of the polynomiality of the MaxCut problem on unit interval graphs by Boyaci, Ekim, and Shalom (2017). Hence, the time complexity of this problem on unit interval graphs remains open. We further provide a better algorithmic upper-bound on the clique-width of mixed unit interval graphs.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GC19-17314J" target="_blank" >GC19-17314J: Geometric Representations of Graphs</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Leibniz International Proceedings in Informatics, LIPIcs
ISBN
978-3-95977-159-7
ISSN
1868-8969
e-ISSN
—
Number of pages
14
Pages from-to
1-14
Publisher name
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Place of publication
Dagstuhl
Event location
Praha
Event date
Aug 24, 2020
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—