The search functionality is under construction.

The search functionality is under construction.

In this paper, we study the following problem: given two graphs *G*, *H* and an isomorphism φ between an induced subgraph of *G* and an induced subgraph of *H*, compute the number of isomorphisms between *G* and *H* that do not contradict φ. We show that this problem can be solved in *O*(((*k*+1)(*k*+1)!)^{2}*n*^{3}) time when the input graphs are restricted to chordal graphs with clique number at most *k*+1. To prove this, we first show that the tree model of a chordal graph can be uniquely constructed in *O*(*n*^{3}) time except for the ordering of children of each node. Then, we show that the number of φ-isomorphisms between *G* and *H* can be efficiently computed by use of the tree model.

- Publication
- IEICE TRANSACTIONS on Information Vol.E85-D No.7 pp.1065-1073

- Publication Date
- 2002/07/01

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- PAPER

- Category
- Algorithms

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

Takayuki NAGOYA, "Counting Graph Isomorphisms among Chordal Graphs with Restricted Clique Number" in IEICE TRANSACTIONS on Information,
vol. E85-D, no. 7, pp. 1065-1073, July 2002, doi: .

Abstract: In this paper, we study the following problem: given two graphs *G*, *H* and an isomorphism φ between an induced subgraph of *G* and an induced subgraph of *H*, compute the number of isomorphisms between *G* and *H* that do not contradict φ. We show that this problem can be solved in *O*(((*k*+1)(*k*+1)!)^{2}*n*^{3}) time when the input graphs are restricted to chordal graphs with clique number at most *k*+1. To prove this, we first show that the tree model of a chordal graph can be uniquely constructed in *O*(*n*^{3}) time except for the ordering of children of each node. Then, we show that the number of φ-isomorphisms between *G* and *H* can be efficiently computed by use of the tree model.

URL: https://global.ieice.org/en_transactions/information/10.1587/e85-d_7_1065/_p

Copy

@ARTICLE{e85-d_7_1065,

author={Takayuki NAGOYA, },

journal={IEICE TRANSACTIONS on Information},

title={Counting Graph Isomorphisms among Chordal Graphs with Restricted Clique Number},

year={2002},

volume={E85-D},

number={7},

pages={1065-1073},

abstract={In this paper, we study the following problem: given two graphs *G*, *H* and an isomorphism φ between an induced subgraph of *G* and an induced subgraph of *H*, compute the number of isomorphisms between *G* and *H* that do not contradict φ. We show that this problem can be solved in *O*(((*k*+1)(*k*+1)!)^{2}*n*^{3}) time when the input graphs are restricted to chordal graphs with clique number at most *k*+1. To prove this, we first show that the tree model of a chordal graph can be uniquely constructed in *O*(*n*^{3}) time except for the ordering of children of each node. Then, we show that the number of φ-isomorphisms between *G* and *H* can be efficiently computed by use of the tree model.},

keywords={},

doi={},

ISSN={},

month={July},}

Copy

TY - JOUR

TI - Counting Graph Isomorphisms among Chordal Graphs with Restricted Clique Number

T2 - IEICE TRANSACTIONS on Information

SP - 1065

EP - 1073

AU - Takayuki NAGOYA

PY - 2002

DO -

JO - IEICE TRANSACTIONS on Information

SN -

VL - E85-D

IS - 7

JA - IEICE TRANSACTIONS on Information

Y1 - July 2002

AB - In this paper, we study the following problem: given two graphs *G*, *H* and an isomorphism φ between an induced subgraph of *G* and an induced subgraph of *H*, compute the number of isomorphisms between *G* and *H* that do not contradict φ. We show that this problem can be solved in *O*(((*k*+1)(*k*+1)!)^{2}*n*^{3}) time when the input graphs are restricted to chordal graphs with clique number at most *k*+1. To prove this, we first show that the tree model of a chordal graph can be uniquely constructed in *O*(*n*^{3}) time except for the ordering of children of each node. Then, we show that the number of φ-isomorphisms between *G* and *H* can be efficiently computed by use of the tree model.

ER -