Improved algorithms for feedback vertex set problems
From MaRDI portal
Publication:955350
DOI10.1016/j.jcss.2008.05.002zbMath1152.68055OpenAlexW1979312598WikidataQ60488742 ScholiaQ60488742MaRDI QIDQ955350
Yang Liu, Songjian Lu, Yngve Villanger, Fedor V. Fomin, Jian'er Chen
Publication date: 19 November 2008
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2008.05.002
Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
On the Complexity of Singly Connected Vertex Deletion ⋮ Linear Time Parameterized Algorithms for Subset Feedback Vertex Set ⋮ A Multivariate Approach for Weighted FPT Algorithms ⋮ Unnamed Item ⋮ Backdoors to Satisfaction ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ On Compiling Structured CNFs to OBDDs ⋮ A multivariate framework for weighted FPT algorithms ⋮ Towards a polynomial kernel for directed feedback vertex set ⋮ A polynomial kernel for block graph deletion ⋮ On compiling structured CNFs to OBDDs ⋮ Kernels for deletion to classes of acyclic digraphs ⋮ Approximation algorithms for orienting mixed graphs ⋮ Beyond bidimensionality: parameterized subexponential algorithms on directed graphs ⋮ Odd cycle transversal in mixed graphs ⋮ Feedback vertex sets on restricted bipartite graphs ⋮ Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization ⋮ A parameterized algorithm for subset feedback vertex set in tournaments ⋮ Unnamed Item ⋮ An FPT algorithm for the vertex cover \(P_4\) problem ⋮ Fixed parameterized algorithms for generalized feedback vertex set problems ⋮ Hardness of subgraph and supergraph problems in \(c\)-tournaments ⋮ Contracting graphs to paths and trees ⋮ FPT algorithms for path-transversal and cycle-transversal problems ⋮ A faster FPT algorithm for bipartite contraction ⋮ An improved parameterized algorithm for the independent feedback vertex set problem ⋮ Confronting intractability via parameters ⋮ Enumerating minimal subset feedback vertex sets ⋮ FPT Algorithms for FVS Parameterized by Split and Cluster Vertex Deletion Sets and Other Parameters ⋮ On feedback vertex set: new measure and new structures ⋮ Two Hardness Results on Feedback Vertex Sets ⋮ Approximation Algorithms for Orienting Mixed Graphs ⋮ Subset Feedback Vertex Set Is Fixed-Parameter Tractable ⋮ Improved FPT Algorithms for Deletion to Forest-Like Structures. ⋮ An improved FPT algorithm for almost forest deletion problem ⋮ On parameterized independent feedback vertex set ⋮ Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation) ⋮ Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms ⋮ Fixed-parameter tractability results for feedback set problems in tournaments ⋮ Faster deterministic \textsc{Feedback Vertex Set} ⋮ Iterative compression and exact algorithms ⋮ An improved FPT algorithm for independent feedback vertex set ⋮ Conflict free version of covering problems on graphs: classical and parameterized ⋮ Mim-width. II. The feedback vertex set problem ⋮ Improved analysis of highest-degree branching for feedback vertex set ⋮ Unnamed Item ⋮ A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems ⋮ A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem ⋮ An FPT algorithm for edge subset feedback edge set ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterised algorithms for deletion to classes of DAGs ⋮ On the complexity of singly connected vertex deletion ⋮ Minimum Cell Connection in Line Segment Arrangements ⋮ An Improved Exact Algorithm for Undirected Feedback Vertex Set ⋮ Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth ⋮ FPT algorithms for generalized feedback vertex set problems ⋮ An improved exact algorithm for undirected feedback vertex set ⋮ On group feedback vertex set parameterized by the size of the cutset
Cites Work
- Finding odd cycle transversals.
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Faster fixed parameter tractable algorithms for finding feedback vertex sets
- Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$
- An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
- ON DISJOINT CYCLES
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Parameterized and Exact Computation
- Computing and Combinatorics
- Exact Computation of Maximum Induced Forest
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
