Sharp separation and applications to exact and parameterized algorithms

DOI10.1007/S00453-011-9555-9zbMath1236.68090DBLPjournals/algorithmica/FominGLS12OpenAlexW1560611630WikidataQ60488521 ScholiaQ60488521MaRDI QIDQ2429363

Fabrizio Grandoni, Fedor V. Fomin, Saket Saurabh, Daniel Lokshtanov

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9555-9

zbMATH Keywords

degree constrained spanning treeseparatorexact and parameterized algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (20)

Spotting Trees with Few Leaves ⋮ A 2k-vertex Kernel for Maximum Internal Spanning Tree ⋮ Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints ⋮ Mixing Color Coding-Related Techniques ⋮ Solving the maximum internal spanning tree problem on interval graphs in polynomial time ⋮ Parameterized algorithms for non-separating trees and branchings in digraphs ⋮ A simple linear time algorithm to solve the MIST problem on interval graphs ⋮ A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem ⋮ A multivariate framework for weighted FPT algorithms ⋮ Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree ⋮ Representative families: a unified tradeoff-based approach ⋮ A Polynomial Time Algorithm for Finding a Spanning Tree with Maximum Number of Internal Vertices on Interval Graphs ⋮ Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs ⋮ An approximation algorithm for maximum internal spanning tree ⋮ Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials ⋮ Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs ⋮ Unnamed Item ⋮ Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree ⋮ Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs ⋮ Approximation algorithms for the maximum weight internal spanning tree problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact exponential algorithms.
• Finding odd cycle transversals.
• Solving connected dominating set faster than \(2^n\)
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• 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
• Solving satisfiability in less than \(2^ n\) steps
• Dynamic programming meets the principle of inclusion and exclusion
• A note on the complexity of the chromatic number problem
• A partial k-arboretum of graphs with bounded treewidth
• New methods for 3-SAT decision and worst-case analysis
• A note on the complexity of minimum dominating set
• Dynamic programming for minimum Steiner trees
• Saving space by algebraization
• A Dynamic Programming Approach to Sequencing Problems
• A measure & conquer approach for the analysis of exact algorithms
• A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
• Divide-and-Color
• Faster Steiner Tree Computation in Polynomial-Space
• Fourier meets M\"{o}bius: fast subset convolution
• Approximating minimum bounded degree spanning trees to within one of optimal
• Sharp Separation and Applications to Exact and Parameterized Algorithms
• Set Partitioning via Inclusion-Exclusion
• A Bottom-Up Method and Fast Algorithms for max independent set
• Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
• A Linear Vertex Kernel for Maximum Internal Spanning Tree
• Algorithms for maximum independent sets
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• A Separator Theorem for Nonplanar Graphs
• Finding a Maximum Independent Set
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• 3-coloring in time
• On Local Search and Placement of Meters in Networks
• Combinatorial bounds via measure and conquer
• An algorithm for the chromatic number of a graph
• Exact Computation of Maximum Induced Forest
• Exact and Parameterized Algorithms for Max Internal Spanning Tree

This page was built for publication: Sharp separation and applications to exact and parameterized algorithms