FPT algorithms for path-transversal and cycle-transversal problems
From MaRDI portal
Publication:456698
DOI10.1016/J.DISOPT.2010.05.003zbMATH Open1248.90072OpenAlexW2025304499MaRDI QIDQ456698FDOQ456698
Authors: 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
Recommendations
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Paths, Trees, and Flowers
- Finding odd cycle transversals.
- Parametrized complexity theory.
- Non-zero disjoint cycles in highly connected group labelled graphs
- Title not available (Why is that?)
- Parameterized graph separation problems
- Packing non-zero \(A\)-paths in group-labelled graphs
- Improved algorithms for feedback vertex set problems
- Title not available (Why is that?)
- On the power of unique 2-prover 1-round games
- An improved parameterized algorithm for the minimum node multiway cut problem
- Iterative Compression for Exactly Solving NP-Hard Minimization Problems
- Title not available (Why is that?)
- Multiway cuts in directed and node weighted graphs
- Algorithms for Multiterminal Cuts
- Approximating unique games
Cited In (22)
- Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
- Designing FPT algorithms for cut problems using randomized contractions
- An improved FPT algorithm for independent feedback vertex set
- What's next? Future directions in parameterized complexity
- A Linear-Time Parameterized Algorithm for Node Unique Label Cover
- Multi-budgeted directed cuts
- Multi-budgeted directed cuts
- Parameterized complexity dichotomy for \textsc{Steiner Multicut}
- A faster parameterized algorithm for Group Feedback Edge Set
- On Weighted Graph Separation Problems and Flow Augmentation
- A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
- A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
- Half-integrality, LP-branching, and FPT algorithms
- On the parameterized complexity of finding separators with non-hereditary properties
- Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes
- FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs
- Title not available (Why is that?)
- Synchronization problems in computer vision with closed-form solutions
- Clique Cover and Graph Separation
- Edge bipartization faster than \(2^k\)
- Parameterized complexity of critical node cuts
- FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
This page was built for publication: FPT algorithms for path-transversal and cycle-transversal problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q456698)
