FPT algorithms for path-transversal and cycle-transversal problems

DOI10.1016/j.disopt.2010.05.003zbMath1248.90072OpenAlexW2025304499MaRDI QIDQ456698

Sylvain Guillemot

Publication date: 16 October 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2010.05.003

zbMATH Keywords

linear programmingfixed-parameter algorithmscut problemsfeedback set problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Related Items (22)

Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ FPT Suspects and Tough Customers: Open Problems of Downey and Fellows ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ A Faster Parameterized Algorithm for Group Feedback Edge Set ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Clique Cover and Graph Separation ⋮ Synchronization problems in computer vision with closed-form solutions ⋮ On Weighted Graph Separation Problems and Flow Augmentation ⋮ A faster FPT algorithm for bipartite contraction ⋮ Edge bipartization faster than \(2^k\) ⋮ On the parameterized complexity of finding separators with non-hereditary properties ⋮ Multi-Budgeted Directed Cuts ⋮ Parameterized complexity of critical node cuts ⋮ A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs ⋮ Unnamed Item ⋮ An improved FPT algorithm for independent feedback vertex set ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs ⋮ A Linear-Time Parameterized Algorithm for Node Unique Label Cover ⋮ Multi-budgeted directed cuts ⋮ Unnamed Item ⋮ On group feedback vertex set parameterized by the size of the cutset

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding odd cycle transversals.
• Parameterized graph separation problems
• Packing non-zero \(A\)-paths in group-labelled graphs
• Improved algorithms for feedback vertex set problems
• An improved parameterized algorithm for the minimum node multiway cut problem
• Parametrized complexity theory.
• Non-zero disjoint cycles in highly connected group labelled graphs
• Algorithms for Multiterminal Cuts
• On the power of unique 2-prover 1-round games
• Approximating unique games
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• Multiway cuts in directed and node weighted graphs
• Paths, Trees, and Flowers

This page was built for publication: FPT algorithms for path-transversal and cycle-transversal problems