Sharp separation and applications to exact and parameterized algorithms
From MaRDI portal
Publication:2429363
DOI10.1007/s00453-011-9555-9zbMath1236.68090OpenAlexW1560611630WikidataQ60488521 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
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
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
