Abstract
The graph reconstruction conjecture is a long-standing open problem in graph theory. There are many algorithmic studies related it besides mathematical studies, such as DECK CHECKING, LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING. We study these algorithmic problems limiting the graph class to interval graphs. Since we can solve GRAPH ISOMORPHISM for interval graphs in polynomial time, DECK CHECKING for interval graphs is easily done in polynomial time. Since the number of interval graphs that can be obtained from an interval graph by adding a vertex and edges incident to it can be exponentially large, developing polynomial time algorithms for LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING on interval graphs is not trivial. We present that these three problems are solvable in polynomial time on interval graphs.
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.
References
Bondy, J.A.: A graph reconstructor’s manual. In: Surveys in Combinatorics. London Mathematical Society Lecture Note Series, vol. 166, pp. 221–252 (1991)
Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences 13, 335–379 (1976)
Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pacific Journal of Mathematics 15, 835–855 (1965)
Harary, F.: A survey of the reconstruction conjecture. Graphs and Combinatorics. Lecture Notes in Mathematics 406, 18–28 (1974)
Kelly, P.J.: A congruence theorem for trees. Pacific Journal of Mathematics 7, 961–968 (1957)
Korte, N., Möhring, R.H.: An incremental linear-time algorithm for recognizing interval graphs. SIAM Journal on Computing 18, 68–81 (1989)
Kratsch, D., Hemaspaandra, L.A.: On the complexity of graph reconstruction. Mathematical Systems Theory 27, 257–273 (1994)
Leckerkerker, C.G., Boland, J.C.: Representation of a finite graph by a set of intervals on the real line. Fundamenta Mathematicae 51, 45–64 (1962)
Lueker, G.S., Booth, K.S.: A linear time algorithm for deciding interval graph isomorphism. Journal of the ACM 26, 183–195 (1979)
von Rimscha, M.: Reconstructibility and perfect graphs. Discrete Mathematics 47, 283–291 (1983)
Uehara, R., Uno, Y.: On computing longest paths in small graph classes. International Journal of Foundations of Computer Science 18, 911–930 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kiyomi, M., Saitoh, T., Uehara, R. (2009). Reconstruction of Interval Graphs. In: Ngo, H.Q. (eds) Computing and Combinatorics. COCOON 2009. Lecture Notes in Computer Science, vol 5609. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02882-3_12
Download citation
DOI: https://doi.org/10.1007/978-3-642-02882-3_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-02881-6
Online ISBN: 978-3-642-02882-3
eBook Packages: Computer ScienceComputer Science (R0)