Abstract
Given an arbitrary graph G=(V,E) and an interval graph H=(V,F) with E ⊆ F we say that H is an interval completion of G. The graph H is called a minimal interval completion of G if, for any sandwich graph H ′ = (V,F ′) with E ⊆ F′ ⊂ F, H ′ is not an interval graph. In this paper we give a \({{\mathcal{O}}(nm)}\) time algorithm computing a minimal interval completion of an arbitrary graph. The output is an interval model of the completion.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Berry, A., Bordat, J.P.: Separability Generalizes Dirac’s Theorem. Discrete Applied Mathematics 84(1-3), 43–53 (1998)
Berry, A., Bordat, J.P.: Local LexBFS Properties in an Arbitrary Graph. Proceedings of Journées Informatiques Messines (2000), http://www.isima.fr/berry/lexbfs.ps
Bodlaender, H.L.: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth. SIAM Journal on Computing 25(6), 1305–1317 (1996)
Cai, L.: Fixed-Parameter Tractability of Graph Modification Problems for Hereditary Properties. Information Processing Letters 58(4), 171–176 (1996)
Gilmore, P.C., Hoffman, A.J.: A characterization of comparability graphs and of interval graphs. Canadian Journal of Mathematics 16, 539–548 (1964)
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, London (1980)
Habib, M., Paul, C., Viennot, L.: Partition Refinement Techniques: An Interesting Algorithmic Tool Kit. International Journal of Foundations of Computer Science 10(2), 147–170 (1999)
Heggernes, P., Mancini, F.: Minimal Split Completions of Graphs. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol. 3887, pp. 592–604. Springer, Heidelberg (2006)
Heggernes, P., Mancini, F., Papadopoulos, C.: Minimal Comparability Completions. Tech. Report, University of Bergen (2006), http://www.ii.uib.no/publikasjoner/texrap/pdf/2006-317.pdf
Heggernes, P., Suchan, K., Todinca, I., Villanger, Y.: Minimal Interval Completions. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 403–414. Springer, Heidelberg (2005)
Heggernes, P., Telle, J.A., Villanger, Y.: Computing minimal triangulations in time O(n α log n) = o(n 2.376). In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms - SODA 2005, pp. 907–916. SIAM, Philadelphia (2005)
Olariu, S.: An optimal greedy heuristic to color interval graphs. Information Processing Letters 37(1), 21–25 (1991)
Rappaport, I., Suchan, K., Todinca, I.: Minimal proper interval completions. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol. 4271, Springer, Heidelberg (2006), www.univ-orleans.fr/SCIENCES/LIFO/prodsci/rapports/RR2006.htm.en
Rose, D., Tarjan, R.E., Lueker, G.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5, 146–160 (1976)
Suchan, K., Todinca, I.: Minimal interval vompletion through graph exploration. Research Report RR 2006-08, Université d’Orléans, www.univ-orleans.fr/SCIENCES/LIFO/prodsci/rapports/RR2006.htm.en
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Suchan, K., Todinca, I. (2006). Minimal Interval Completion Through Graph Exploration. In: Asano, T. (eds) Algorithms and Computation. ISAAC 2006. Lecture Notes in Computer Science, vol 4288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11940128_52
Download citation
DOI: https://doi.org/10.1007/11940128_52
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49694-6
Online ISBN: 978-3-540-49696-0
eBook Packages: Computer ScienceComputer Science (R0)