Computer Science – Discrete Mathematics
Scientific paper
2007-04-12
Dans Lecture Notes In Computer Science - 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'07),
Computer Science
Discrete Mathematics
Scientific paper
10.1007/978-3-540-74839-7_6
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, ...
Gambette Philippe
Vialette Stéphane
No associations
LandOfFree
On restrictions of balanced 2-interval graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On restrictions of balanced 2-interval graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On restrictions of balanced 2-interval graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-147934