An exact algorithm for subgraph homeomorphism
(2009) In Journal of Discrete Algorithms 7(4). p.464468 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) vertexdisjoint 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 fixedvertex subgraph homeomorphism.
We show that fixedvertex 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 nontrivial 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) vertexdisjoint 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 fixedvertex subgraph homeomorphism.
We show that fixedvertex 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 nontrivial upper bounds on the time complexity of the problem of finding k vertexdisjoint paths and general subgraph homeomorphism. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/1670334
 author
 Lingas, Andrzej ^{LU} and Wahlén, Martin ^{LU}
 organization
 publishing date
 2009
 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
 15708667
 DOI
 10.1016/j.jda.2008.10.003
 project
 VR 20084649
 language
 English
 LU publication?
 yes
 id
 1665260188384a2d8a6a193ec8d91c62 (old id 1670334)
 date added to LUP
 20100913 13:50:29
 date last changed
 20161013 04:29:54
@misc{1665260188384a2d8a6a193ec8d91c62, 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) vertexdisjoint 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 fixedvertex subgraph homeomorphism.<br/><br> <br/><br> We show that fixedvertex 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 nontrivial upper bounds on the time complexity of the problem of finding k vertexdisjoint paths and general subgraph homeomorphism.}, author = {Lingas, Andrzej and Wahlén, Martin}, issn = {15708667}, keyword = {Subgraph homeomorphism,Disjoint paths,Time complexity,Space complexity}, language = {eng}, number = {4}, pages = {464468}, 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}, }