Algorithms by layer-decomposition for the subgraph recognition problem with attributes

Yifan Xu

doi:10.3934/jimo.2005.1.337

Article Contents

2005, Volume 1, Issue 3: 337-343. Doi: 10.3934/jimo.2005.1.337

This issue Previous Article A-shaped bin packing: Worst case analysis via simulation Next Article Optimal preemptive online scheduling to minimize lp norm on two processors

Algorithms by layer-decomposition for the subgraph recognition problem with attributes

Yifan Xu^1,

1.
School of Management, Fudan University, Shanghai 200433

Received: August 2004

Revised: January 2005

Published: July 2005

Abstract Related Papers Cited by

Abstract

Given two planar graphs $G$ and $H$, the subgraph recognition problem (SRP) is concerned with finding all isomorphic subgraphs of $H$ in $G$. Using the idea of layer-decomposition, we develop algorithms for SRP that have computational complexity $O(n(\Delta-1)^{k-1})$, where $\Delta$ is the degree of $G$ and $n, k$ are the orders of $G, H$ respectively.

Keywords:

Mathematics Subject Classification: 20L05, 20L13.

Citation:

Article Metrics

HTML views() PDF downloads(71) Cited by(0)

Algorithms by layer-decomposition for the subgraph recognition problem with attributes

Abstract

Access History

Article Metrics

Access History

Other Articles By Authors

Catalog

Algorithms by layer-decomposition for the subgraph recognition problem with attributes

Abstract

Access History

SHARE

Article Metrics

Access History

Other Articles By Authors

Catalog

Export File

Citation

Format

Content