The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

An exact algorithm for subgraph homeomorphism

På svenska

Author

Summary, in English

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.

Department/s

  • Computer Science

Publishing year

2009

Language

English

Pages

464-468

Publication/Series

Journal of Discrete Algorithms

Volume

7

Issue

4

Document type

Journal article

Publisher

Elsevier

Topic

  • Computer Science

Keywords

  • Subgraph homeomorphism
  • Disjoint paths
  • Time complexity
  • Space complexity

Status

Published

Project

  • VR 2008-4649

ISBN/ISSN/Other

  • ISSN: 1570-8667