Finding odd cycle transversals.
From MaRDI portal
Publication:703225
DOI10.1016/j.orl.2003.10.009zbMath1052.05061WikidataQ56209810 ScholiaQ56209810MaRDI QIDQ703225
Adrian Vetta, Bruce A. Reed, Kaleigh Smith
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
05C38: Paths and cycles
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Related Items
The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number, Fixed-Parameter Algorithms for Cluster Vertex Deletion, A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems, Separator-based data reduction for signed graph balancing, Parameterized coloring problems on chordal graphs, Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, Approximate min-max relations for odd cycles in planar graphs, Efficient algorithms for counting parameterized list \(H\)-colorings, Improved algorithms for feedback vertex set problems, Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs, Chordal deletion is fixed-parameter tractable, Fixed-parameter algorithms for cluster vertex deletion, Constant ratio fixed-parameter approximation of the edge multicut problem, Parameterizing above or below guaranteed values, Parameterized complexity of finding regular induced subgraphs, Almost 2-SAT is fixed-parameter tractable, Iterative compression and exact algorithms, Planar graph bipartization in linear time, Subset Feedback Vertex Set Is Fixed-Parameter Tractable, Measuring Indifference: Unit Interval Vertex Deletion, Speeding up Exact Algorithms With High Probability, 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], Iterative Compression and Exact Algorithms, Iterative Compression for Exactly Solving NP-Hard Minimization Problems, Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs
Cites Work
