Reconstruction Algorithms for Permutation Graphs and Distance-Hereditary Graphs

スポンサーリンク

概要

• 論文の詳細を見る

• 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(n^8) time algorithm for PREIMAGE CONSTRUCTION on permutation graphs and an O(n^4(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(n^2) edges, the input size is O(n^3) (, 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.

著者

• KIYOMI Masashi

  International College of Arts and Sciences, Yokohama City University

• UEHARA Ryuhei

  School of Information Science

• SAITOH Toshiki

  Department of Electrical and Electronic Engineering, Graduate School of Engineering, Kobe University

関連論文

• Bipartite powers of interval bigraphs
• 22D-11-1 The Alteration of Drug Disposition in Rabbits during Acute Phase Response.
• Longest Path Problems on Ptolemaic Graphs
• FOREWORD
• Voronoi Game on a Path
• Hardness results and an exact exponential algorithm for the spanning tree congestion problem (コンピュテーション)
• NP-completeness of generalized Kaboozle
• Reconstruction Algorithms for Permutation Graphs and Distance-Hereditary Graphs
• Computational Complexity of Piano-Hinged Dissections
• Reconstruction Algorithms for Permutation Graphs and Distance-Hereditary Graphs

スポンサーリンク