On group feedback vertex set parameterized by the size of the cutset

DOI10.1007/s00453-014-9966-5zbMath1336.68121arXiv1112.6255OpenAlexW2049332363MaRDI QIDQ262251

Marcin Pilipczuk, Marek Cygan, Michał Pilipczuk

Publication date: 29 March 2016

Published in: Algorithmica, Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1112.6255

zbMATH Keywords

fixed-parameter tractabilitygraph-separation problemsgroup feedback vertex set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A Faster Parameterized Algorithm for Group Feedback Edge Set ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Synchronization problems in computer vision with closed-form solutions ⋮ On Weighted Graph Separation Problems and Flow Augmentation ⋮ A faster FPT algorithm for bipartite contraction ⋮ An improved FPT algorithm for independent feedback vertex set ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ On group feedback vertex set parameterized by the size of the cutset

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On group feedback vertex set parameterized by the size of the cutset
• FPT algorithms for path-transversal and cycle-transversal problems
• Packing cycles with modularity constraints
• Finding odd cycle transversals.
• Parameterized graph separation problems
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Packing non-zero \(A\)-paths in group-labelled graphs
• Improved algorithms for feedback vertex set problems
• Almost 2-SAT is fixed-parameter tractable
• An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
• Non-zero disjoint cycles in highly connected group labelled graphs
• Half-integrality, LP-branching, and FPT Algorithms
• On Multiway Cut Parameterized above Lower Bounds
• Faster fixed parameter tractable algorithms for finding feedback vertex sets
• Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• A fixed-parameter algorithm for the directed feedback vertex set problem
• On Feedback Vertex Set New Measure and New Structures
• ON DISJOINT CYCLES
• Representative Sets and Irrelevant Vertices
• Parameterized and Exact Computation
• Linear-Time FPT Algorithms via Network Flow
• Half-integrality, LP-branching and FPT Algorithms
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

This page was built for publication: On group feedback vertex set parameterized by the size of the cutset