Spotting Trees with Few Leaves
(2015) International Colloquium on Automata, Languages, and Programming 9134. p.243-255- Abstract
- 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... (More)
- 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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/7516038
- author
- Björklund, Andreas LU ; Kamat, Vikram ; Kowalik, Lukasz and Zehavi, Meirav
- organization
- publishing date
- 2015
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Lecture Notes in Computer Science/Automata, Languages, and Programming
- editor
- Haldorsson, Magnus. M. ; Iwama, Kazou ; Kobayashi, Naoki and Speckmann, Bettina
- volume
- 9134
- pages
- 243 - 255
- publisher
- Springer
- conference name
- International Colloquium on Automata, Languages, and Programming
- conference dates
- 2015-07-08
- external identifiers
-
- wos:000364317700020
- scopus:84950132799
- ISSN
- 0302-9743
- 1611-3349
- ISBN
- 978-3-662-47672-7
- DOI
- 10.1007/978-3-662-47672-7_20
- project
- Exact algorithms
- language
- English
- LU publication?
- yes
- id
- d0e966b8-c9e3-4c0f-a007-6d3db95b72ec (old id 7516038)
- date added to LUP
- 2016-04-01 10:56:49
- date last changed
- 2024-05-06 01:26:06
@inproceedings{d0e966b8-c9e3-4c0f-a007-6d3db95b72ec,
abstract = {{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.}},
author = {{Björklund, Andreas and Kamat, Vikram and Kowalik, Lukasz and Zehavi, Meirav}},
booktitle = {{Lecture Notes in Computer Science/Automata, Languages, and Programming}},
editor = {{Haldorsson, Magnus. M. and Iwama, Kazou and Kobayashi, Naoki and Speckmann, Bettina}},
isbn = {{978-3-662-47672-7}},
issn = {{0302-9743}},
language = {{eng}},
pages = {{243--255}},
publisher = {{Springer}},
title = {{Spotting Trees with Few Leaves}},
url = {{http://dx.doi.org/10.1007/978-3-662-47672-7_20}},
doi = {{10.1007/978-3-662-47672-7_20}},
volume = {{9134}},
year = {{2015}},
}