On exact complexity of subgraph homeomorphism
(2007) 4th International Conference, TAMC 2007 In Theory and Applications of Models of Computation / Lecture Notes in Computer Science 4484. p.256261 Abstract
 The subgraph homeomorphism problem is to decide whether 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 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 O(2n − pnO(1)) or in time O(3n − pn6) and polynomial space. In effect, we obtain new nontrivial upper timebounds on the exact complexity... (More)  The subgraph homeomorphism problem is to decide whether 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 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 O(2n − pnO(1)) or in time O(3n − pn6) and polynomial space. In effect, we obtain new nontrivial upper timebounds on the exact 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/587893
 author
 Lingas, Andrzej ^{LU} and Wahlén, Martin ^{LU}
 organization
 publishing date
 2007
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 Theory and Applications of Models of Computation / Lecture Notes in Computer Science
 editor
 Cai, Jinyi; Cooper, Barry and Zhu, Hong
 volume
 4484
 pages
 256  261
 publisher
 Springer
 conference name
 4th International Conference, TAMC 2007
 external identifiers

 WOS:000246671900023
 Scopus:35448973245
 ISBN
 9783540725039
 DOI
 10.1007/9783540725046_23
 project
 VR 20054085
 language
 English
 LU publication?
 yes
 id
 49ea25287f3247e1995e74218864f3d9 (old id 587893)
 alternative location
 http://www.springerlink.com/content/9853653753736560/fulltext.pdf
 date added to LUP
 20071106 11:36:59
 date last changed
 20161013 04:45:15
@misc{49ea25287f3247e1995e74218864f3d9, abstract = {The subgraph homeomorphism problem is to decide whether 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 is termed fixedvertex subgraph homeomorphism.<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 O(2n − pnO(1)) or in time O(3n − pn6) and polynomial space. In effect, we obtain new nontrivial upper timebounds on the exact complexity of the problem of finding k vertexdisjoint paths and general subgraph homeomorphism.}, author = {Lingas, Andrzej and Wahlén, Martin}, editor = {Cai, Jinyi and Cooper, Barry and Zhu, Hong}, isbn = {9783540725039}, language = {eng}, pages = {256261}, publisher = {ARRAY(0x8e04b28)}, series = {Theory and Applications of Models of Computation / Lecture Notes in Computer Science}, title = {On exact complexity of subgraph homeomorphism}, url = {http://dx.doi.org/10.1007/9783540725046_23}, volume = {4484}, year = {2007}, }