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, K 1,5-free graphs, ...
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Rebea, A.B.: Étude des stables dans les graphes quasi-adjoints. PhD thesis, Université de Grenoble (1981)
Blin, G., Fertin, G., Vialette, S.: New results for the 2-interval pattern problem. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol. 3109, Springer, Heidelberg (2004)
Butman, A., Hermelin, D., Lewenstein, M., Rawitz, D.: Optimization problems in multiple-interval graphs. In: Proceedings of SODA 2007, pp. 268–277 (2007)
Brandstädt, A., Le, V.B., Szymczak, T., Siegemund, F., de Ridder, H.N., Knorr, S., Rzehak, M., Mowitz, M., Ryabova, N.: ISGCI: Information System on Graph Class Inclusions. http://wwwteo.informatik.uni-rostock.de/isgci/classes.cgi
Bafna, V., Narayanan, B.O., Ravi, R.: Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles). Discrete Applied Math. 71(1), 41–54 (1996)
Bar-Yehuda, R., Halldórson, M.M., Naor, J., Shachnai, H., Shapira, I.: Scheduling split intervals. SIAM Journal on Computing 36(1), 1–15 (2006)
Crochemore, M., Hermelin, D., Landau, G.M., Vialette, S.: Approximating the 2-interval pattern problem. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 426–437. Springer, Heidelberg (2005)
Corneil, D.G., Kim, H., Natarajan, S., Olariu, S., Sprague, A.P.: Simple linear time recognition of unit interval graphs. Information Processing Letters 55, 99–104 (1995)
Chudnovsky, M., Seymour, P.: The structure of claw-free graphs. In: Surveys in Combinatorics. London. Math. Soc. Lecture Notes, vol. 327, pp. 153–172. Cambridge University Press, Cambridge (2005)
Faudree, R., Flandrin, E., Ryjáček, Z.: Claw-free graphs - a survey. Discrete Mathematics 164, 87–147 (1997)
Griggs, J.R., West, D.B.: Extremal values of the interval number of a graph. SIAM Journal on Algebraic and Discrete Methods 1, 1–7 (1980)
Gyárfás, A., West, D.B.: Multitrack interval graphs. Congress Numerantium 109, 109–116 (1995)
Halldórsson, M.M., Karlsson, R.K.: Strip graphs: Recognition and scheduling. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol. 4271, pp. 137–146. Springer, Heidelberg (2006)
Joseph, D., Meidanis, J., Tiwari, P.: Determining DNA sequence similarity using maximum independent set algorithms for interval graphs. In: Nurmi, O., Ukkonen, E. (eds.) SWAT 1992. LNCS, vol. 621, pp. 326–337. Springer, Heidelberg (1992)
Karp, R.M.: Reducibility among combinatorial problems, pp. 85–103. Plenum Press, New York (1972)
Karlsson, R.: A survey of split intervals and related graphs, Manuscript (2005)
King, A., Reed, B.: Bounding χ in terms of ω ans δ for quasi-line graphs. Article in preparation (2007)
Kostochka, A.V., West, D.B.: Every outerplanar graph is the union of two interval graphs. Congress Numerantium 139, 5–8 (1999)
Lovász, L.: Kneser’s conjecture, chromatic number, and homotopy. Journal of Combinatorial Theory Series A 25, 319–324 (1978)
McGuigan, R.: Presentation at NSF-CBMS Conference at Colby College (1977)
Roberts, F.S.: Indifference graphs. In: Proof Techniques in Graph Theory, Proceedings of the Second Ann Arbor Graph Theory Conference, pp. 139–146 (1969)
Vialette, S.: Aspects algorithmiques de la prédiction des structures secondaires d’ARN. PhD thesis, Université Paris 7 (2001)
Vialette, S.: On the computational complexity of 2-interval pattern matching. Theoretical Computer Science 312(2-3), 223–249 (2004)
West, D.B., Shmoys, D.B.: Recognizing graphs with fixed interval number is NP-complete. Discrete Applied Math. 8, 295–305 (1984)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gambette, P., Vialette, S. (2007). On Restrictions of Balanced 2-Interval Graphs. In: Brandstädt, A., Kratsch, D., Müller, H. (eds) Graph-Theoretic Concepts in Computer Science. WG 2007. Lecture Notes in Computer Science, vol 4769. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74839-7_6
Download citation
DOI: https://doi.org/10.1007/978-3-540-74839-7_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74838-0
Online ISBN: 978-3-540-74839-7
eBook Packages: Computer ScienceComputer Science (R0)