On Restrictions of Balanced 2-Interval Graphs

DOI10.1007/978-3-540-74839-7_6MaRDI QIDQ3508554zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Philippe Gambette, Stéphane Vialette

Publication date 1 July 2008

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0704.1571

zbMATH Keywords

schedulingbioinformaticsgraph classesline graphsclaw-free graphscircular interval graphsquasi-line graphs2-interval graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: The class of 2-interval graphs has been introduced for modelling scheduling and allocation problems, and more recently for specific bioinformatic problems. Some of those applications imply restrictions on the 2-interval graphs, and justify the introduction of a hierarchy of subclasses of 2-interval graphs that generalize line graphs: balanced 2-interval graphs, unit 2-interval graphs, and (x,x)-interval graphs. We provide instances that show that all the inclusions are strict. We extend the NP-completeness proof of recognizing 2-interval graphs to the recognition of balanced 2-interval graphs. Finally we give hints on the complexity of unit 2-interval graphs recognition, by studying relationships with other graph classes: proper circular-arc, quasi-line graphs, K_{1,5}-free graphs, ...

Recommendations

• Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
• Recognizing d-interval graphs and d-track interval graphs
• Bounded representations of interval and proper interval graphs
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Interval bigraphs and circular arc graphs

Cited in

(6)

• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• On line graphs of subcubic triangle-free graphs
• New Infinite Families of 2-Edge-Balanced Graphs
• Recognizing unit multiple interval graphs is hard
• Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
• Recognizing d-interval graphs and d-track interval graphs

This page was built for publication: On Restrictions of Balanced 2-Interval Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3508554)