Advanced

An exact algorithm for subgraph homeomorphism

Lingas, Andrzej LU and Wahlén, Martin LU (2009) In Journal of Discrete Algorithms 7(4). p.464-468
Abstract
The subgraph homeomorphism problem is to decide if there is an injective mapping of the vertices of a pattern graph into vertices of a host graph so that the edges of the pattern graph can be mapped into (internally) vertex-disjoint paths in the host graph. The restriction of subgraph homeomorphism where an injective mapping of the vertices of the pattern graph into vertices of the host graph is already given in the input instance is termed fixed-vertex subgraph homeomorphism.



We show that fixed-vertex subgraph homeomorphism for a pattern graph on p vertices and a host graph on n vertices can be solved in time 2n−pnO(1) or in time 3n−pnO(1) and polynomial space. In effect, we obtain new non-trivial upper bounds on the... (More)
The subgraph homeomorphism problem is to decide if there is an injective mapping of the vertices of a pattern graph into vertices of a host graph so that the edges of the pattern graph can be mapped into (internally) vertex-disjoint paths in the host graph. The restriction of subgraph homeomorphism where an injective mapping of the vertices of the pattern graph into vertices of the host graph is already given in the input instance is termed fixed-vertex subgraph homeomorphism.



We show that fixed-vertex subgraph homeomorphism for a pattern graph on p vertices and a host graph on n vertices can be solved in time 2n−pnO(1) or in time 3n−pnO(1) and polynomial space. In effect, we obtain new non-trivial upper bounds on the time complexity of the problem of finding k vertex-disjoint paths and general subgraph homeomorphism. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Subgraph homeomorphism, Disjoint paths, Time complexity, Space complexity
in
Journal of Discrete Algorithms
volume
7
issue
4
pages
464 - 468
publisher
Elsevier
external identifiers
  • Scopus:70349774746
ISSN
1570-8667
DOI
10.1016/j.jda.2008.10.003
project
VR 2008-4649
language
English
LU publication?
yes
id
16652601-8838-4a2d-8a6a-193ec8d91c62 (old id 1670334)
date added to LUP
2010-09-13 13:50:29
date last changed
2016-10-13 04:29:54
@misc{16652601-8838-4a2d-8a6a-193ec8d91c62,
  abstract     = {The subgraph homeomorphism problem is to decide if there is an injective mapping of the vertices of a pattern graph into vertices of a host graph so that the edges of the pattern graph can be mapped into (internally) vertex-disjoint paths in the host graph. The restriction of subgraph homeomorphism where an injective mapping of the vertices of the pattern graph into vertices of the host graph is already given in the input instance is termed fixed-vertex subgraph homeomorphism.<br/><br>
<br/><br>
We show that fixed-vertex subgraph homeomorphism for a pattern graph on p vertices and a host graph on n vertices can be solved in time 2n−pnO(1) or in time 3n−pnO(1) and polynomial space. In effect, we obtain new non-trivial upper bounds on the time complexity of the problem of finding k vertex-disjoint paths and general subgraph homeomorphism.},
  author       = {Lingas, Andrzej and Wahlén, Martin},
  issn         = {1570-8667},
  keyword      = {Subgraph homeomorphism,Disjoint paths,Time complexity,Space complexity},
  language     = {eng},
  number       = {4},
  pages        = {464--468},
  publisher    = {ARRAY(0xa141df8)},
  series       = {Journal of Discrete Algorithms},
  title        = {An exact algorithm for subgraph homeomorphism},
  url          = {http://dx.doi.org/10.1016/j.jda.2008.10.003},
  volume       = {7},
  year         = {2009},
}