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.

Spotting Trees with Few Leaves

In English

Författare

  • Andreas Björklund
  • Vikram Kamat
  • Lukasz Kowalik
  • Meirav Zehavi

Redaktör

  • Magnus. M. Haldorsson
  • Kazou Iwama
  • Naoki Kobayashi
  • Bettina Speckmann

Summary, in English

We show two results related to the Hamiltonicity and k -Path algorithms in undirected graphs by Björklund [FOCS’10], and Björklund et al., [arXiv’10]. First, we demonstrate that the technique used can be generalized to finding some k-vertex tree with l leaves in an n-vertex undirected graph in O∗(1.657^k2^{l/2}) time. It can be applied as a subroutine to solve the k -Internal Spanning Tree (k-IST) problem in O∗(min(3.455^k,1.946^n)) time using polynomial space, improving upon previous algorithms for this problem. In particular, for the first time, we break the natural barrier of O∗(2^n). Second, we show that the iterated random bipartition employed by the algorithm can be improved whenever the host graph admits a vertex coloring with few colors; it can be an ordinary proper vertex coloring, a fractional vertex coloring, or a vector coloring. In effect, we show improved bounds for k-Path and Hamiltonicity in any graph of maximum degree Δ=4,…,12 or with vector chromatic number at most 8.

Publiceringsår

2015

Språk

Engelska

Sidor

243-255

Publikation/Tidskrift/Serie

Lecture Notes in Computer Science/Automata, Languages, and Programming

Volym

9134

Dokumenttyp

Konferensbidrag

Förlag

Springer

Ämne

  • Computer Science

Conference name

International Colloquium on Automata, Languages, and Programming

Conference date

2015-07-08

Status

Published

Projekt

  • Exact algorithms

Forskningsgrupp

  • Algorithms

ISBN/ISSN/Övrigt

  • ISSN: 1611-3349
  • ISSN: 0302-9743
  • ISBN: 978-3-662-47672-7