Spotting Trees with Few Leaves

DOI10.1137/15M1048975zbMath1362.05078OpenAlexW2605336159MaRDI QIDQ5346548

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

Publication date: 24 May 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/15m1048975

zbMATH Keywords

Hamiltonian cyclecoloringfractional coloring\(k\)-pathparameterized complexityalgebraic techniquesvector coloring\(k\)-internal spanning tree

Mathematics Subject Classification ID

Trees (05C05) Nonnumerical algorithms (68W05) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Eulerian and Hamiltonian graphs (05C45)

Related Items (4)

Exact Algorithms for the Minimum Load Spanning Tree Problem ⋮ The Asymmetric Travelling Salesman Problem In Sparse Digraphs. ⋮ Unnamed Item ⋮ Approximate Counting of k-Paths: Deterministic and in Polynomial Space

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure
• 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
• Minimum leaf out-branching and related problems
• Three short proofs in graph theory
• A probabilistic remark on algebraic program testing
• A linear vertex kernel for maximum internal spanning tree
• 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
• Sharp separation and applications to exact and parameterized algorithms
• A note on the complexity of minimum dominating set
• The fractional chromatic number of triangle-free subcubic graphs
• 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
• An Upper Bound on the Fractional Chromatic Number of Triangle-Free Subcubic Graphs
• Probably optimal graph motifs
• The Fractional Chromatic Number of Graphs of Maximum Degree at Most Three
• Approximation Algorithms and Semidefinite Programming
• Approximating the Longest Cycle Problem in Sparse Graphs
• A 2k-vertex Kernel for Maximum Internal Spanning Tree
• 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
• On Linear Time Minor Tests with Depth-First Search
• Color-coding
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Fast Hamiltonicity Checking Via Bases of Perfect Matchings
• 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
• Subcubic triangle-free graphs have fractional chromatic number at most 14/5
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Parameterized Algorithms
• Exact Computation of Maximum Induced Forest

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