Sökning: id:"swepub:oai:lup.lub.lu.se:d0e966b8-c9e3-4c0f-a007-6d3db95b72ec" >
Spotting Trees with...
Spotting Trees with Few Leaves
-
- Björklund, Andreas (författare)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
Kamat, Vikram (författare)
-
Kowalik, Lukasz (författare)
-
visa fler...
-
Zehavi, Meirav (författare)
-
Haldorsson, Magnus. M. (redaktör/utgivare)
-
Iwama, Kazou (redaktör/utgivare)
-
Kobayashi, Naoki (redaktör/utgivare)
-
Speckmann, Bettina (redaktör/utgivare)
-
visa färre...
-
(creator_code:org_t)
- 2015-06-20
- 2015
- Engelska.
-
Ingår i: Lecture Notes in Computer Science/Automata, Languages, and Programming. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. - 9783662476727 ; 9134, s. 243-255
- Relaterad länk:
-
http://dx.doi.org/10... (free)
-
visa fler...
-
http://arxiv.org/pdf...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publikations- och innehållstyp
- kon (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas