Sharp separation and applications to exact and parameterized algorithms
From MaRDI portal
Recommendations
- Sharp separation and applications to exact and parameterized algorithms
- New Sharpness Properties, Algorithms and Complexity Bounds for Partitioning Shortest Path Procedures
- An algorithmic separating hyperplane theorem and its applications
- Faster exact algorithms for hard problems: A parameterized point of view
- scientific article; zbMATH DE number 4189228
- Polynomial time approximation schemes and parameterized complexity
- Mathematical Foundations of Computer Science 2004
- Revisiting separation: algorithms and complexity
- Sharp threshold results for computational complexity
Cites work
- scientific article; zbMATH DE number 5776838 (Why is no real title available?)
- scientific article; zbMATH DE number 1261820 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- 3-coloring in time
- A Dynamic Programming Approach to Sequencing Problems
- A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
- A Separator Theorem for Nonplanar Graphs
- A Separator Theorem for Planar Graphs
- A bottom-up method and fast algorithms for Max Independent Set
- A linear vertex kernel for Maximum Internal Spanning Tree
- A measure \& conquer approach for the analysis of exact algorithms
- A note on the complexity of minimum dominating set
- A note on the complexity of the chromatic number problem
- A partial k-arboretum of graphs with bounded treewidth
- Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
- Algorithms for maximum independent sets
- An algorithm for the chromatic number of a graph
- Applications of a Planar Separator Theorem
- Approximating minimum bounded degree spanning trees to within one of optimal
- Approximating the Minimum-Degree Steiner Tree to within One of Optimal
- Combinatorial bounds via measure and conquer
- Design by measure and conquer. A faster exact algorithm for dominating set
- Divide-and-Color
- Dynamic programming for minimum Steiner trees
- Dynamic programming meets the principle of inclusion and exclusion
- Exact Computation of Maximum Induced Forest
- Exact and parameterized algorithms for Max Internal Spanning Tree
- Exact exponential algorithms.
- Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
- Faster Steiner Tree Computation in Polynomial-Space
- Finding a Maximum Independent Set
- Finding odd cycle transversals.
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- Fourier meets M\"{o}bius: fast subset convolution
- Improved algorithms for path, matching, and packing problems
- Minimum leaf out-branching and related problems
- New methods for 3-SAT decision and worst-case analysis
- On Local Search and Placement of Meters in Networks
- On the minimum feedback vertex set problem: Exact and enumeration algorithms
- Reducing to independent set structure -- the case of \(k\)-internal spanning tree
- Saving space by algebraization
- Set partitioning via inclusion-exclusion
- Sharp separation and applications to exact and parameterized algorithms
- Solving connected dominating set faster than \(2^n\)
- Solving satisfiability in less than \(2^ n\) steps
Cited in
(21)- Solving the maximum internal spanning tree problem on interval graphs in polynomial time
- A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem
- Patching colors with tensors
- Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials
- Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs
- Fast algorithms for parameterized problems with relaxed disjointness constraints
- A \(2k\)-vertex kernel for maximum internal spanning tree
- Spotting trees with few leaves
- 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
- Parameterized single-exponential time polynomial space algorithm for Steiner tree
- Parameterized algorithms for non-separating trees and branchings in digraphs
- A simple linear time algorithm to solve the MIST problem on interval graphs
- An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth
- New Sharpness Properties, Algorithms and Complexity Bounds for Partitioning Shortest Path Procedures
- Mixing Color Coding-Related Techniques
- A Polynomial Time Algorithm for Finding a Spanning Tree with Maximum Number of Internal Vertices on Interval Graphs
- Sharp separation and applications to exact and parameterized algorithms
- A multivariate framework for weighted FPT algorithms
- Representative families: a unified tradeoff-based approach
- Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs
This page was built for publication: Sharp separation and applications to exact and parameterized algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2429363)
