Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
From MaRDI portal
Recommendations
Cites work
- \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Algorithm Theory - SWAT 2004
- Algorithms and Data Structures
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
- Computing and Combinatorics
- Experimental and Efficient Algorithms
- Finding odd cycle transversals.
- Fixed-parameter tractability results for feedback set problems in tournaments
- Graph-Theoretic Concepts in Computer Science
- scientific article; zbMATH DE number 6118220 (Why is no real title available?)
- scientific article; zbMATH DE number 5158512 (Why is no real title available?)
- scientific article; zbMATH DE number 5158513 (Why is no real title available?)
- scientific article; zbMATH DE number 125608 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 1979503 (Why is no real title available?)
- scientific article; zbMATH DE number 1467487 (Why is no real title available?)
- scientific article; zbMATH DE number 2090012 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Introduction to algorithms
- Mathematical Foundations of Computer Science 2004
- ON DISJOINT CYCLES
- On enumerating all minimal solutions of feedback problems
- On the power of unique 2-prover 1-round games
- Optimization, approximation, and complexity classes
- Parameterized algorithms for feedback set problems and their duals in tournaments
- Parameterized and Exact Computation
- Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
- The approximation of maximum subgraph problems
Cited in
(71)- Parameterized complexity of finding regular induced subgraphs
- An improved FPT algorithm for almost forest deletion problem
- Faster deterministic \textsc{Feedback Vertex Set}
- Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
- On the complexity of singly connected vertex deletion
- An improved deterministic parameterized algorithm for cactus vertex deletion
- Fixed-parameter tractability results for feedback set problems in tournaments
- Iterative compression and exact algorithms
- Mim-width. II. The feedback vertex set problem
- Faster graph bipartization
- An improved exact algorithm for undirected feedback vertex set
- Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
- A polynomial kernel for block graph deletion
- An improved parameterized algorithm for the independent feedback vertex set problem
- Odd cycle transversal in mixed graphs
- Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs
- Circumventing connectivity for kernelization
- An Improved Exact Algorithm for Undirected Feedback Vertex Set
- On polynomial kernels for structural parameterizations of odd cycle transversal
- FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
- What's next? Future directions in parameterized complexity
- A quartic kernel for pathwidth-one vertex deletion
- A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width
- A Linear Kernel for Planar Feedback Vertex Set
- Iterative Compression and Exact Algorithms
- Iterative Compression for Exactly Solving NP-Hard Minimization Problems
- A note on the parameterized complexity of unordered maximum tree orientation
- When recursion is better than iteration: a linear-time algorithm for acyclicity with few error vertices
- Generalized pseudoforest deletion: algorithms and uniform kernel
- Confronting intractability via parameters
- A fixed-parameter algorithm for the vertex cover P₃ problem
- On feedback vertex set: new measure and new structures
- A parameterized complexity view on collapsing \(k\)-cores
- On the Complexity of Singly Connected Vertex Deletion
- Covering vectors by spaces in perturbed graphic matroids and their duals
- scientific article; zbMATH DE number 7278081 (Why is no real title available?)
- scientific article; zbMATH DE number 7286685 (Why is no real title available?)
- The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number
- Algorithms and Data Structures
- Theoretical Computer Science
- Compression via matroids: a randomized polynomial kernel for odd cycle transversal
- Slightly superexponential parameterized problems
- Incompressibility of H-free edge modification problems: towards a dichotomy
- A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
- An improved FPT algorithm for independent feedback vertex set
- Finding k-secluded trees faster
- Improved FPT Algorithms for Deletion to Forest-Like Structures.
- A parameterized algorithm for subset feedback vertex set in tournaments
- Minimization and parameterized variants of vertex partition problems on graphs
- Finding \(k\)-secluded trees faster
- Separator-based data reduction for signed graph balancing
- A survey of parameterized algorithms and the complexity of edge modification
- Vertex cover problem parameterized above and below tight bounds
- Improved FPT Algorithms for Deletion to Forest-Like Structures
- The complexity of König subgraph problems and above-guarantee vertex cover
- Edge bipartization faster than \(2^k\)
- Hitting long directed cycles is fixed-parameter tractable
- Nonpartisan feedback vertex set
- FPT algorithms for connected feedback vertex set
- Hitting meets packing: how hard can it be?
- Solving subset feedback vertex set in chordal graphs faster than 2ᵏ
- Subset feedback vertex set parameterized by multiway cut is FPT
- Parameterized complexity of feedback vertex set with connectivity constraints
- Nonpartisan feedback vertex set
- A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem
- A parameterized complexity view on collapsing \(k\)-cores
- An FPT algorithm for the vertex cover \(P_4\) problem
- Improved algorithms for feedback vertex set problems
- Fixed-parameter enumerability of cluster editing and related problems
- Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs
- Chordal deletion is fixed-parameter tractable
This page was built for publication: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q856420)
