Abstract | ||
---|---|---|
The class of 2-interval graphs has been introduced for modelling scheduling and allocation problems, and more recently for specific bioinformatics 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 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, K1,5-free graphs, . . . |
Year | DOI | Venue |
---|---|---|
2007 | 10.1007/978-3-540-74839-7_6 | workshop on graph-theoretic concepts in computer science |
Keywords | DocType | Volume |
interval graph,line graph,unit 2-interval graph,scheduling.,circular interval graphs,claw-free graphs,5-free graph,quasi-line graphs,modelling scheduling,2-interval graph,2-interval graphs,graph class,graph classes,bioinformatics,allocation problem,line graphs,unit 2-interval graphs recognition,np-completeness proof,scheduling | Conference | abs/0704.1571 |
ISSN | ISBN | Citations |
Dans Lecture Notes In Computer Science - 33rd International
Workshop on Graph-Theoretic Concepts in Computer Science (WG'07), Dornburg :
Allemagne (2007) | 3-540-74838-5 | 3 |
PageRank | References | Authors |
0.38 | 14 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Philippe Gambette | 1 | 77 | 9.61 |
Stéphane Vialette | 2 | 648 | 48.10 |