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
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Tomoki IMADA, Hiroshi NAGAMOCHI, "Indexing All Rooted Subgraphs of a Rooted Graph" in IEICE TRANSACTIONS on Information,
vol. E95-D, no. 3, pp. 712-721, March 2012, doi: 10.1587/transinf.E95.D.712.
Abstract: 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
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E95.D.712/_p
Copy
@ARTICLE{e95-d_3_712,
author={Tomoki IMADA, Hiroshi NAGAMOCHI, },
journal={IEICE TRANSACTIONS on Information},
title={Indexing All Rooted Subgraphs of a Rooted Graph},
year={2012},
volume={E95-D},
number={3},
pages={712-721},
abstract={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
keywords={},
doi={10.1587/transinf.E95.D.712},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Indexing All Rooted Subgraphs of a Rooted Graph
T2 - IEICE TRANSACTIONS on Information
SP - 712
EP - 721
AU - Tomoki IMADA
AU - Hiroshi NAGAMOCHI
PY - 2012
DO - 10.1587/transinf.E95.D.712
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E95-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2012
AB - 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
ER -