Another disjoint compression algorithm for odd cycle transversal

DOI10.1016/J.IPL.2013.08.007MaRDI QIDQ2445321zbMATH OpenOpenAlexFDO

Authors R. Krithika, N. S. Narayanaswamy

Publication date 14 April 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2013.08.007

zbMATH Keywords

graph algorithmsparameterized complexityabove guarantee vertex coverodd cycle transversaldisjoint compression

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Finding odd cycle transversals.
• scientific article; zbMATH DE number 6297714
• Hitting selected (odd) cycles
• Compression via Matroids
• Simpler parameterized algorithm for OCT

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A complexity dichotomy for finding disjoint solutions of vertex deletion problems
• Algorithm Engineering for Optimal Graph Bipartization
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Faster parameterized algorithms using linear programming
• Finding odd cycle transversals.
• Simpler parameterized algorithm for OCT

Cited in

(6)

• The parameterized complexity of finding point sets with hereditary properties
• An FPT algorithm for the vertex cover \(P_4\) problem
• Simpler parameterized algorithm for OCT
• Approximability of clique transversal in perfect graphs
• Compression via Matroids
• Finding odd cycle transversals.

This page was built for publication: Another disjoint compression algorithm for odd cycle transversal

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