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 in the algorithmic aspects of the conjecture. We present an O(n6) time algorithm for PREIMAGE CONSTRUCTION on permutation graphs. A simplified algorithm can be applied for PREIMAGE CONSTRUCTION on distancehereditary graphs. There are polynomial time isomorphism algorithms for permutation graphs. However the number of permutation graphs obtained by adding a vertex to a permutation graph may be 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.

• 一般社団法人情報処理学会の論文
• 2009-09-08

著者

• Ryuhei Uehara

  School Of Information Science Japan Advanced Institute Of Science And Technology

• Uehara Ryuhei

  School Of Information Science Japan Advanced Institute Of Science And Technology

• Toshiki Saitoh

  Japan Advanced Institute Of Science And Technology

• Ryuhei Uehara

  Japan Advanced Institute of Science and Technology

• Masashi Kiyomi

  Japan Advanced Institute Of Science And Technology

• Toshiki Saitoh

  Graduate School of Engineering, Kobe University

関連論文

• Graph Orientation Problems for Multiple st-Reachability
• Efficient Enumeration of All Pseudoline Arrangements
• The Complexity of Free Flood Filling Games
• Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
• Approximating the path-distance-width for k-cocomparability graphs
• On the number of reduced trees, cographs, and series-parallel graphs by compression
• Reconstruction Algorithms for Permutation Graphs and Distance-Hereditary Graphs
• Computational Complexity of Piano-Hinged Dissections
• Bumpy Pyramid Folding Problem
• Intersection dimension of bipartite graphs

スポンサーリンク