Spotting Trees with Few Leaves

DOI10.1007/978-3-662-47672-7_20zbMath1441.68066arXiv1501.00563OpenAlexW1913856675MaRDI QIDQ3448789

Andreas Björklund, Łukasz Kowalik, Vikram Kamat, Meirav Zehavi

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1501.00563

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Spotting Trees with Few Leaves ⋮ Narrow sieves for parameterized paths and packings ⋮ Representative families: a unified tradeoff-based approach ⋮ Parameterized algorithms for list \(K\)-cycle ⋮ Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials ⋮ Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
• Three short proofs in graph theory
• A probabilistic remark on algebraic program testing
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• Narrow sieves for parameterized paths and packings
• A note on the complexity of minimum dominating set
• Algorithms for k-Internal Out-Branching
• Fast Witness Extraction Using a Decision Oracle
• Representative Sets of Product Families
• Representative Families: A Unified Tradeoff-Based Approach
• Probably optimal graph motifs
• Approximation Algorithms and Semidefinite Programming
• Spotting Trees with Few Leaves
• A 2k-vertex Kernel for Maximum Internal Spanning Tree
• Mixing Color Coding-Related Techniques
• The Travelling Salesman Problem in Bounded Degree Graphs
• Faster Algebraic Algorithms for Path and Packing Problems
• An Improved Exact Algorithm for Cubic Graph TSP
• The Operator $\Psi$ for the Chromatic Number of a Graph
• Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
• Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Color-coding
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On the Number of Hamilton Cycles in Bounded Degree Graphs
• The Traveling Salesman Problem for Cubic Graphs
• Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
• Determinant Sums for Undirected Hamiltonicity
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Exact Computation of Maximum Induced Forest

This page was built for publication: Spotting Trees with Few Leaves