IEICE TRANSACTIONS on Information
Reconstruction Algorithms for Permutation Graphs and Distance-Hereditary Graphs
Summary :
PREIMAGE CONSTRUCTION problem by Kratsch and Hemaspaandra naturally arose from the famous graph reconstruction conjecture. It deals with the algorithmic aspects of the conjecture. We present an O(n8) time algorithm for PREIMAGE CONSTRUCTION on permutation graphs and an O(n4(n+m)) time algorithm for PREIMAGE CONSTRUCTION on distance-hereditary graphs, where n is the number of graphs in the input, and m is the number of edges in a preimage. Since each graph of the input has n-1 vertices and O(n2) edges, the input size is O(n3) (, or O(nm)). There are polynomial time isomorphism algorithms for permutation graphs and distance-hereditary graphs. However the number of permutation (distance-hereditary) graphs obtained by adding a vertex to a permutation (distance-hereditary) graph is generally exponentially large. Thus exhaustive checking of these graphs does not achieve any polynomial time algorithm. Therefore reducing the number of preimage candidates is the key point.
- Publication
- IEICE TRANSACTIONS on Information Vol.E96-D No.3 pp.426-432
- Publication Date
- 2013/03/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E96.D.426
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Masashi KIYOMI, Toshiki SAITOH, Ryuhei UEHARA, "Reconstruction Algorithms for Permutation Graphs and Distance-Hereditary Graphs" in IEICE TRANSACTIONS on Information,
vol. E96-D, no. 3, pp. 426-432, March 2013, doi: 10.1587/transinf.E96.D.426.
Abstract: PREIMAGE CONSTRUCTION problem by Kratsch and Hemaspaandra naturally arose from the famous graph reconstruction conjecture. It deals with the algorithmic aspects of the conjecture. We present an O(n8) time algorithm for PREIMAGE CONSTRUCTION on permutation graphs and an O(n4(n+m)) time algorithm for PREIMAGE CONSTRUCTION on distance-hereditary graphs, where n is the number of graphs in the input, and m is the number of edges in a preimage. Since each graph of the input has n-1 vertices and O(n2) edges, the input size is O(n3) (, or O(nm)). There are polynomial time isomorphism algorithms for permutation graphs and distance-hereditary graphs. However the number of permutation (distance-hereditary) graphs obtained by adding a vertex to a permutation (distance-hereditary) graph is generally exponentially large. Thus exhaustive checking of these graphs does not achieve any polynomial time algorithm. Therefore reducing the number of preimage candidates is the key point.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E96.D.426/_p
Copy
@ARTICLE{e96-d_3_426,
author={Masashi KIYOMI, Toshiki SAITOH, Ryuhei UEHARA, },
journal={IEICE TRANSACTIONS on Information},
title={Reconstruction Algorithms for Permutation Graphs and Distance-Hereditary Graphs},
year={2013},
volume={E96-D},
number={3},
pages={426-432},
abstract={PREIMAGE CONSTRUCTION problem by Kratsch and Hemaspaandra naturally arose from the famous graph reconstruction conjecture. It deals with the algorithmic aspects of the conjecture. We present an O(n8) time algorithm for PREIMAGE CONSTRUCTION on permutation graphs and an O(n4(n+m)) time algorithm for PREIMAGE CONSTRUCTION on distance-hereditary graphs, where n is the number of graphs in the input, and m is the number of edges in a preimage. Since each graph of the input has n-1 vertices and O(n2) edges, the input size is O(n3) (, or O(nm)). There are polynomial time isomorphism algorithms for permutation graphs and distance-hereditary graphs. However the number of permutation (distance-hereditary) graphs obtained by adding a vertex to a permutation (distance-hereditary) graph is generally exponentially large. Thus exhaustive checking of these graphs does not achieve any polynomial time algorithm. Therefore reducing the number of preimage candidates is the key point.},
keywords={},
doi={10.1587/transinf.E96.D.426},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Reconstruction Algorithms for Permutation Graphs and Distance-Hereditary Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 426
EP - 432
AU - Masashi KIYOMI
AU - Toshiki SAITOH
AU - Ryuhei UEHARA
PY - 2013
DO - 10.1587/transinf.E96.D.426
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E96-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2013
AB - PREIMAGE CONSTRUCTION problem by Kratsch and Hemaspaandra naturally arose from the famous graph reconstruction conjecture. It deals with the algorithmic aspects of the conjecture. We present an O(n8) time algorithm for PREIMAGE CONSTRUCTION on permutation graphs and an O(n4(n+m)) time algorithm for PREIMAGE CONSTRUCTION on distance-hereditary graphs, where n is the number of graphs in the input, and m is the number of edges in a preimage. Since each graph of the input has n-1 vertices and O(n2) edges, the input size is O(n3) (, or O(nm)). There are polynomial time isomorphism algorithms for permutation graphs and distance-hereditary graphs. However the number of permutation (distance-hereditary) graphs obtained by adding a vertex to a permutation (distance-hereditary) graph is generally exponentially large. Thus exhaustive checking of these graphs does not achieve any polynomial time algorithm. Therefore reducing the number of preimage candidates is the key point.
ER -
English
