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
