Reconstruction of Interval Graphs

DOI10.1007/978-3-642-02882-3_12zbMath1248.05125OpenAlexW2208060184MaRDI QIDQ5323055

Toshiki Saitoh, Ryuhei Uehara, Masashi Kiyomi

Publication date: 23 July 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02882-3_12

zbMATH Keywords

polynomial-time algorithminterval graphsgraph isomorphismgraph reconstruction conjecturelegitimate deckdeck checkingpreimage constructionpreimage counting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (2)

Reconstruction of interval graphs ⋮ An elementary proof of Jin's theorem with a bound

Cites Work

• Unnamed Item
• Reconstructibility and perfect graphs
• A congruence theorem for trees
• 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
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• On the complexity of graph reconstruction

This page was built for publication: Reconstruction of Interval Graphs