Reconstruction of interval graphs

DOI10.1016/j.tcs.2010.07.006zbMath1198.05114OpenAlexW2087050979MaRDI QIDQ604467

Masashi Kiyomi, Ryuhei Uehara, Toshiki Saitoh

Publication date: 11 November 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.07.006

zbMATH Keywords

polynomial time algorithminterval graphsgraph reconstruction conjecture

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Unnamed Item
• Unnamed Item
• Reconstructibility and perfect graphs
• A congruence theorem for trees
• Complexity results in graph reconstruction
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Incidence matrices and interval graphs
• ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES
• Representation of a finite graph by a set of intervals on the real line
• Reconstruction Algorithm for Permutation Graphs
• Almost every graph has reconstruction number three
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• On the complexity of graph reconstruction
• Reconstruction of Interval Graphs

This page was built for publication: Reconstruction of interval graphs