Spotting Trees with Few Leaves
(2015) International Colloquium on Automata, Languages, and Programming In Lecture Notes in Computer Science/Automata, Languages, and Programming 9134. p.243255 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 kvertex tree with l leaves in an nvertex undirected graph in O∗(1.657^k2^{l/2}) time. It can be applied as a subroutine to solve the k Internal Spanning Tree (kIST) 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 kvertex tree with l leaves in an nvertex undirected graph in O∗(1.657^k2^{l/2}) time. It can be applied as a subroutine to solve the k Internal Spanning Tree (kIST) 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 kPath 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:
http://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
 in
 Lecture Notes in Computer Science/Automata, Languages, and Programming
 editor
 Haldorsson, Magnus. M.; Iwama, Kazou; Kobayashi, Naoki; Speckmann, Bettina; ; ; and
 volume
 9134
 pages
 243  255
 publisher
 Springer
 conference name
 International Colloquium on Automata, Languages, and Programming
 external identifiers

 wos:000364317700020
 scopus:84950132799
 ISSN
 16113349
 03029743
 ISBN
 9783662476727
 DOI
 10.1007/9783662476727_20
 project
 Exact algorithms
 language
 English
 LU publication?
 yes
 id
 d0e966b8c9e34c0fa0076d3db95b72ec (old id 7516038)
 date added to LUP
 20150720 10:17:38
 date last changed
 20180107 04:37:55
@inproceedings{d0e966b8c9e34c0fa0076d3db95b72ec, 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 kvertex tree with l leaves in an nvertex undirected graph in O∗(1.657^k2^{l/2}) time. It can be applied as a subroutine to solve the k Internal Spanning Tree (kIST) 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 kPath 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 = {9783662476727}, issn = {16113349}, language = {eng}, pages = {243255}, publisher = {Springer}, title = {Spotting Trees with Few Leaves}, url = {http://dx.doi.org/10.1007/9783662476727_20}, volume = {9134}, year = {2015}, }