Indexing All Rooted Subgraphs of a Rooted Graph

スポンサーリンク

概要

• 論文の詳細を見る

• Let G be a connected graph in which we designate a vertex or a block (a biconnected component) as the center of G. For each cut-vertex v, let Gv be the connected subgraph induced from G by v and the vertices that will be separated from the center by removal of v, where v is designated as the root of Gv. We consider the set R of all such rooted subgraphs in G, and assign an integer, called an index, to each of the subgraphs so that two rooted subgraphs in R receive the same indices if and only if they are isomorphic under the constraint that their roots correspond each other. In this paper, assuming a procedure for computing a signature of each graph in a class G of biconnected graphs, we present a framework for computing indices to all rooted subgraphs of a graph G with a center which is composed of biconnected components from G. With this framework, we can find indices to all rooted subgraphs of a outerplanar graph with a center in linear time and space.

• 2012-03-01

著者

• Nagamochi Hiroshi

  Graduate School Of Informatics Kyoto University

• Imada Tomoki

  Graduate School Of Informatics Kyoto University

関連論文

• Constant Time Generation of Trees with Degree Bounds
• Constant Time Generation of Trees with Degree Bounds
• Enumerating Colored and Rooted Outerplanar Graphs
• Survivable Network Design Problems with Weighted Degree Constraints (Combinatorial Optimization and Discrete Algorithms)
• Contention-Free λ-Planes in Optically Burst-Switched WDM Networks(Internet)
• The Next-to-Shortest Path in Undirected Graphs with Nonnegative Weights
• Accelerating A* algorithms by sweeping out small-degree nodes
• Indexing All Rooted Subgraphs of a Rooted Graph

スポンサーリンク