Reconstructing Cactus Graphs from Shortest Path Information

DOI10.1007/978-3-319-41168-2_13zbMath1476.68212OpenAlexW2491586093MaRDI QIDQ2830066

Yun Lu, Evangelos Kranakis, Danny Krizanc

Publication date: 9 November 2016

Published in: Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-41168-2_13

zbMATH Keywords

cactus graphgraph reconstructionshortest path information

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A divide-and-conquer approach for reconstruction of \(\{C_{ \geq 5}\}\)-free graphs via betweenness queries, Reconstructibility of unrooted level-\(k\) phylogenetic networks from distances

Cites Work

• Unnamed Item
• Unnamed Item
• Reconstructibility and perfect graphs
• A congruence theorem for trees
• Le problème d'étoiles pour graphes est NP-complèt
• Combinatorics and graph theory. Proceedings of the Symposium Held at the Indian Statistical Institute, Calcutta, February 25--29, 1980
• The splittance of a graph
• Split graphs
• The reconstruction of outerplanar graphs
• Centdian Computation in Cactus Graphs
• On the complexity of reconstructing H-free graphs from their Star Systems
• A remark on the existence of finite graphs
• Almost every graph has reconstruction number three
• A Characterization of the degree sequences of 2-trees
• Sequences Characterizing k-Trees
• Reconstructing a Graph from its Neighborhood Lists
• Graph reconstruction with a betweenness oracle
• Graph Reconstruction via Distance Oracles
• Reconstruction of Cacti