On restrictions of balanced 2-interval graphs
| dc.creator | Gambette, Philippe | |
| dc.creator | Vialette, Stéphane | |
| dc.date | 2007-04-12 | |
| dc.date | 2007-06-11 | |
| dc.date.accessioned | 2026-07-07T09:18:05Z | |
| dc.date.available | 2026-07-07T09:18:05Z | |
| dc.description | 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, ... | |
| dc.identifier | https://arxiv.org/abs/0704.1571 | |
| dc.identifier | http://arxiv.org/abs/0704.1571 | |
| dc.identifier | Dans Lecture Notes In Computer Science - 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'07), Dornburg : Allemagne (2007) | |
| dc.identifier | doi:10.1007/978-3-540-74839-7_6 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/153899 | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Quantitative Methods | |
| dc.title | On restrictions of balanced 2-interval graphs | |
| dc.type | text |