Finding odd cycle transversals.
From MaRDI portal
Publication:703225
DOI10.1016/j.orl.2003.10.009zbMath1052.05061OpenAlexW2051856222WikidataQ56209810 ScholiaQ56209810MaRDI QIDQ703225
Adrian Vetta, Kaleigh Smith, Bruce A. Reed
Publication date: 11 January 2005
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.orl.2003.10.009
Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
Parameterized coloring problems on chordal graphs ⋮ Linear kernels for separating a graph into components of bounded size ⋮ On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal ⋮ An improved deterministic parameterized algorithm for cactus vertex deletion ⋮ Clique cycle-transversals in distance-hereditary graphs ⋮ Chordal editing is fixed-parameter tractable ⋮ Streaming deletion problems parameterized by vertex cover ⋮ A Basic Parameterized Complexity Primer ⋮ Backdoors to Satisfaction ⋮ Studies in Computational Aspects of Voting ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property ⋮ Towards constant-factor approximation for chordal/distance-hereditary vertex deletion ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization ⋮ Optimizing adiabatic quantum program compilation using a graph-theoretic framework ⋮ Reducing rank of the adjacency matrix by graph modification ⋮ Bivariate Complexity Analysis of Almost Forest Deletion ⋮ Reducing Rank of the Adjacency Matrix by Graph Modification ⋮ Distance from triviality 2.0: hybrid parameterizations ⋮ Reoptimization of parameterized problems ⋮ List-coloring -- parameterizing from triviality ⋮ A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ Approximate min-max relations for odd cycles in planar graphs ⋮ A polynomial kernel for block graph deletion ⋮ Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion} ⋮ Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs ⋮ Clique Cover and Graph Separation ⋮ Beyond bidimensionality: parameterized subexponential algorithms on directed graphs ⋮ FPT algorithms to compute the elimination distance to bipartite graphs and more ⋮ Odd cycle transversal in mixed graphs ⋮ Parameterized complexity of vertex deletion into perfect graph classes ⋮ Separator-based data reduction for signed graph balancing ⋮ Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization ⋮ Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel ⋮ Bivariate complexity analysis of \textsc{Almost Forest Deletion} ⋮ On the parameterized vertex cover problem for graphs with perfect matching ⋮ Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters ⋮ FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs ⋮ Wheel-Free Deletion Is W[2-Hard] ⋮ Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover ⋮ Parameterized complexity of finding connected induced subgraphs ⋮ Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion ⋮ Obtaining a planar graph by vertex deletion ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs ⋮ A note on the parameterized complexity of unordered maximum tree orientation ⋮ An FPT algorithm for the vertex cover \(P_4\) problem ⋮ A randomized polynomial kernel for subset feedback vertex set ⋮ Feedback Vertex Sets in Tournaments ⋮ Fair allocation of indivisible items with conflict graphs ⋮ FPT algorithms for path-transversal and cycle-transversal problems ⋮ Another disjoint compression algorithm for odd cycle transversal ⋮ A faster FPT algorithm for bipartite contraction ⋮ The complexity of König subgraph problems and above-guarantee vertex cover ⋮ An improved parameterized algorithm for the independent feedback vertex set problem ⋮ Confronting intractability via parameters ⋮ Backdoor Sets for CSP. ⋮ Efficient algorithms for counting parameterized list \(H\)-colorings ⋮ A fixed-parameter algorithm for the vertex cover \(P_3\) problem ⋮ Odd Multiway Cut in Directed Acyclic Graphs ⋮ Edge bipartization faster than \(2^k\) ⋮ New bounds for the signless Laplacian spread ⋮ On feedback vertex set: new measure and new structures ⋮ Improved kernel results for some FPT problems based on simple observations ⋮ Subset Feedback Vertex Set Is Fixed-Parameter Tractable ⋮ An improved FPT algorithm for almost forest deletion problem ⋮ Improved algorithms for feedback vertex set problems ⋮ List H-coloring a graph by removing few vertices ⋮ Paths to trees and cacti ⋮ On parameterized independent feedback vertex set ⋮ Planar graph bipartization in linear time ⋮ Augmenting tractable fragments of abstract argumentation ⋮ Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs ⋮ Chordal deletion is fixed-parameter tractable ⋮ Faster deterministic \textsc{Feedback Vertex Set} ⋮ Iterative compression and exact algorithms ⋮ Iterative Compression and Exact Algorithms ⋮ Fixed-parameter algorithms for cluster vertex deletion ⋮ Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems ⋮ Measuring Indifference: Unit Interval Vertex Deletion ⋮ Constant ratio fixed-parameter approximation of the edge multicut problem ⋮ Approximability of clique transversal in perfect graphs ⋮ Parameterizing above or below guaranteed values ⋮ A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem ⋮ Faster graph bipartization ⋮ Parameterized Complexity of Vertex Deletion into Perfect Graph Classes ⋮ Iterative Compression for Exactly Solving NP-Hard Minimization Problems ⋮ Parameterized complexity of finding regular induced subgraphs ⋮ Parity Linkage and the Erdős-Pósa Property of Odd Cycles Through Prescribed Vertices in Highly Connected Graphs ⋮ Almost 2-SAT is fixed-parameter tractable ⋮ Important Separators and Parameterized Algorithms ⋮ Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs ⋮ Parameterized complexity of independent set in H-free graphs ⋮ Tournaments and Semicomplete Digraphs ⋮ On the complexity of singly connected vertex deletion ⋮ Fixed-parameter tractability for subset feedback set problems with parity constraints ⋮ Speeding up Exact Algorithms With High Probability ⋮ A fast branching algorithm for cluster vertex deletion ⋮ On group feedback vertex set parameterized by the size of the cutset ⋮ Paths to Trees and Cacti ⋮ On the Complexity of Singly Connected Vertex Deletion ⋮ Finding branch-decompositions of matroids, hypergraphs, and more ⋮ Hitting Selected (Odd) Cycles ⋮ An Updated Experimental Evaluation of Graph Bipartization Methods ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ First-order Logic with Connectivity Operators ⋮ Graph Bipartization Problem with Applications to Via Minimization in VLSI Design ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams ⋮ On Weighted Graph Separation Problems and Flow Augmentation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number ⋮ Chordless Cycle Packing Is Fixed-Parameter Tractable ⋮ Parameterized Complexity of Independent Set in H-Free Graphs. ⋮ Exploring the Kernelization Borders for Hitting Cycles ⋮ On the Parameterized Complexity of Clique Elimination Distance ⋮ Slightly Superexponential Parameterized Problems ⋮ Unnamed Item ⋮ Conflict free version of covering problems on graphs: classical and parameterized ⋮ Your rugby mates don't need to know your colleagues: triadic closure with edge colors ⋮ Fixed-Parameter Algorithms for Cluster Vertex Deletion ⋮ A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Finding Branch-Decompositions of Matroids, Hypergraphs, and More ⋮ Unnamed Item
Cites Work
