Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

On exact complexity of subgraph homeomorphism

In English

Författare

Redaktör

  • Jin-yi Cai
  • Barry Cooper
  • Hong Zhu

Summary, in English

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) 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 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 O(2n − pnO(1)) or in time O(3n − pn6) and polynomial space. In effect, we obtain new non-trivial upper time-bounds on the exact complexity of the problem of finding k vertex-disjoint paths and general subgraph homeomorphism.

Avdelning/ar

  • Computer Science

Publiceringsår

2007

Språk

Engelska

Sidor

256-261

Publikation/Tidskrift/Serie

Theory and Applications of Models of Computation / Lecture Notes in Computer Science

Volym

4484

Dokumenttyp

Konferensbidrag

Förlag

Springer

Ämne

  • Computer Science

Conference name

4th International Conference, TAMC 2007

Conference date

2007-05-22 - 2007-05-25

Conference place

Shanghai, China

Status

Published

Projekt

  • VR 2005-4085

ISBN/ISSN/Övrigt

  • ISBN: 978-3-540-72503-9