
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Indexing All Rooted Subgraphs of a Rooted Graph
Tomoki IMADA Hiroshi NAGAMOCHI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E95D
No.3
pp.712721 Publication Date: 2012/03/01
Online ISSN: 17451361
DOI: 10.1587/transinf.E95.D.712
Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science – Mathematical Foundations and Applications of Computer Science and Algorithms –) Category: Keyword: graph isomorphism, index, rooted graphs, outerplanar graphs, signature,
Full Text: PDF(228KB)>>
Summary:
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 cutvertex v, let G_{v} 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 G_{v}. 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 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 . With this framework, we can find indices to all rooted subgraphs of a outerplanar graph with a center in linear time and space.

