Reconstruction of interval graphs

DOI10.1016/J.TCS.2010.07.006MaRDI QIDQ604467zbMATH OpenOpenAlexFDO

Authors Masashi Kiyomi, Toshiki Saitoh, Ryuhei Uehara

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

graph reconstruction conjectureinterval graphspolynomial time algorithm

Mathematics Subject Classification ID

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

Recommendations

• Reconstruction of Interval Graphs
• On the complexity of graph reconstruction
• On the reconstruction of graph invariants
• 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
• Almost every graph has reconstruction number three
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Complexity results in graph reconstruction
• scientific article; zbMATH DE number 17789 (Why is no real title available?)
• scientific article; zbMATH DE number 3458693 (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
• Reconstruction Algorithm for Permutation Graphs
• Reconstruction of Interval 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

(2)

• 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 Q604467)