Reconstruction of Interval Graphs

DOI10.1007/978-3-642-02882-3_12MaRDI QIDQ5323055zbMATH OpenOpenAlexFDO

Authors Masashi Kiyomi, Toshiki Saitoh, Ryuhei Uehara

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

deck checkinggraph isomorphismgraph reconstruction conjectureinterval graphslegitimate deckpolynomial-time algorithmpreimage constructionpreimage counting

Mathematics Subject Classification ID

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

Recommendations

• Reconstruction of interval graphs
• On the complexity of graph reconstruction
• scientific article; zbMATH DE number 2061158
• Reconstruction Algorithm for Permutation Graphs
• scientific article; zbMATH DE number 3841911

Cites work

• A congruence theorem for trees
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• scientific article; zbMATH DE number 17789 (Why is no real title available?)
• Incidence matrices and interval graphs
• On computing longest paths in small graph classes
• On the complexity of graph reconstruction
• Reconstructibility and perfect graphs
• Representation of a finite graph by a set of intervals on the real line
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(4)

• scientific article; zbMATH DE number 3841911 (Why is no real title available?)
• An elementary proof of Jin's theorem with a bound
• On the complexity of graph reconstruction
• Reconstruction of interval graphs

This page was built for publication: Reconstruction of Interval Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5323055)