FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs

DOI10.1007/978-3-540-79723-4_13MaRDI QIDQ3503584zbMATH OpenOpenAlexFDO

Authors Sylvain Guillemot

Publication date 5 June 2008

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-79723-4_13

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• FPT algorithms for path-transversal and cycle-transversal problems
• FPT-algorithms for minimum-bends tours
• scientific article; zbMATH DE number 7310159
• Polynomial time algorithm for constructing vertex-disjoint paths in transposition graphs
• FPT algorithms for domination in biclique-free graphs
• Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
• FPT algorithms for domination in sparse graphs and beyond
• Algorithms for shortest paths and d-cycle problems
• FPT algorithms for generalized feedback vertex set problems
• Algorithms for solving problems on graphs of bounded pathwidth

Cites work

• An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
• Approximating unique games
• Finding odd cycle transversals.
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• Multiway cuts in directed and node weighted graphs
• On the power of unique 2-prover 1-round games
• Packing non-zero \(A\)-paths in group-labelled graphs
• Parameterized graph separation problems
• Parametrized complexity theory.

Cited in

(7)

• The critical node detection problem in networks: a survey
• FPT algorithms to compute the elimination distance to bipartite graphs and more
• Improved FPT Algorithms for Rectilinear k-Links Spanning Path
• FPT algorithms for path-transversal and cycle-transversal problems
• Multicut Is FPT
• Compression via matroids: a randomized polynomial kernel for odd cycle transversal
• Simple and improved parameterized algorithms for multiterminal cuts

This page was built for publication: FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3503584)