Abstract
We characterize graphs that have intersection representations using unit intervals with open or closed ends such that all ends of the intervals are integral in terms of infinitely many minimal forbidden induced subgraphs. Furthermore, we provide a quadratic-time algorithm that decides if a given interval graph admits such an intersection representation.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
Classification of the topic
References
Halldórsson, M.M., Patt-Shamir, B., Rawitz, D.: Online Scheduling with Interval Conflicts, in. In: Proceedings of the 28th Annual Conference on Theoretical Aspects of Computer Science (STACS), pp. 472–483 (2011)
Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (1999)
Corneil, D.G., Kim, H., Natarajan, S., Olariu, S., Sprague, A.P.: Simple linear time recognition of unit interval graphs. Inf. Process. Lett. 55, 99–104 (1995)
Corneil, D.G., Olariu, S., Stewart, L.: The ultimate interval graph recognition algorithm? (Extended abstract). In: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 175–180 (1998)
Corneil, D.G.: A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs. Discrete Appl. Math. 138, 371–379 (2004)
Dourado, M.C., Le, V.B., Protti, F., Rautenbach, D., Szwarcfiter, J.L.: Mixed unit interval graphs. manuscript (2011)
Frankl, P., Maehara, H.: Open-interval graphs versus closed-interval graphs. Discrete Math. 63, 97–100 (1987)
Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pacific J. Math. 15, 835–855 (1965)
Goldberg, P.W., Golumbic, M.C., Kaplan, H., Shamir, R.: Four strikes against physical mapping of DNA. J. Comput. Biol. 2, 139–152 (1995)
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, Amsterdam, The Netherlands. Annals of Discrete Mathematics, vol. 57 (2004)
Heggernes, P., Suchan, K., Todinca, I., Villanger, Y.: Characterizing Minimal Interval Completions. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol. 4393, pp. 236–247. Springer, Heidelberg (2007)
Hell, P., Shamir, R., Sharan, R.: A fully dynamic algorithm for recognizing and representing proper interval graphs. SIAM J. Comput. 31, 289–305 (2001)
Herrera de Figueiredo, C.M., Meidanis, J., Picinin de Mello, C.: A linear-time algorithm for proper interval graph recognition. Inf. Process. Lett. 56, 179–184 (1995)
Kaplan, H., Shamir, R.: Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques. SIAM J. Comput. 25, 540–561 (1996)
Kendall, D.G.: Incidence matrices, interval graphs, and seriation in archaeology. Pacific J. Math. 28, 565–570 (1969)
Kratsch, D., Stewart, L.: Approximating Bandwidth by Mixing Layouts of Interval Graphs. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 248–258. Springer, Heidelberg (1999)
Krokhin, A.A., Jeavons, P.G., Jonsson, P.: The Complexity of Constraints on Intervals and Lengths. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol. STACS 2002, pp. 443–454. Springer, Heidelberg (2002)
Papadimitriou, C.H., Yannakakis, M.: Scheduling interval-ordered tasks. SIAM J. Comput. 8, 405–409 (1979)
Rautenbach, D., Szwarcfiter, J.L.: Unit Interval Graphs - A Story with Open Ends. In: European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2011). Electronic Notes in Discrete Mathematics, vol. 38, pp. 737–742 (2011)
Roberts, F.S.: Indifference graphs. In: Harary, F. (ed.) Proof Techniques in Graph Theory, pp. 139–146. Academic Press (1969)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Le, V.B., Rautenbach, D. (2012). Integral Mixed Unit Interval Graphs. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds) Computing and Combinatorics. COCOON 2012. Lecture Notes in Computer Science, vol 7434. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32241-9_42
Download citation
DOI: https://doi.org/10.1007/978-3-642-32241-9_42
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32240-2
Online ISBN: 978-3-642-32241-9
eBook Packages: Computer ScienceComputer Science (R0)