Algorithm to Generate All Connected Simple Graphs of Given Order

スポンサーリンク

概要

• 論文の詳細を見る

• We present an efficient algorithm to generate connected simple graphs of given order. It is based on the reverse search technique and a new vertex partitioning strategy. By implementing the algorithm in C, we can generate all connected simple graphs of order 11 in five and a half hours.

• 2013-02-22

著者

• Takeaki Uno

  National Institute Of Informatics

• Takeaki Uno

  Principles of Informatics Research Division, National Institute of Informatics

• Tetsushi Matsui

  Principles of Informatics Research Division, National Institute of Informatics

関連論文

• The Complexity of Free Flood Filling Games
• Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
• On the number of reduced trees, cographs, and series-parallel graphs by compression
• Algorithm to Generate All Connected Simple Graphs of Given Order
• An Algorithm for Finding Frequently Appearing Long String Patterns from Large Scale Databases
• Toward Constant Time Enumeration

スポンサーリンク