Cycle transversals in bounded degree graphs

MaRDI QIDQ5403054zbMATH OpenFDO

Authors Marina Groshaus, Sulamita Klein, Fábio Protti, Pavol Hell, Loana T. Nogueira

Publication date 25 March 2014

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1534/0.html

zbMATH Keywords

approximation algorithmscycle-transversalstransversals

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Cycle transversals in bounded degree graphs
• Approximating Maximum Subgraphs without Short Cycles
• Approximating maximum subgraphs without short cycles
• Cycle transversals in perfect graphs and cographs
• Kernelization for cycle transversal problems

Cited in

(9)

• Cycle transversals in perfect graphs and cographs
• Transversals of longest cycles in chordal and bounded tree-width graphs
• Odd cycle transversal in mixed graphs
• Cycle transversals in bounded degree graphs
• Clique cycle-transversals in distance-hereditary graphs
• Complexity of cycle transverse matching problems
• Approximating maximum subgraphs without short cycles
• Approximating Maximum Subgraphs without Short Cycles
• On 3-degree 4-chordal graphs

This page was built for publication: Cycle transversals in bounded degree graphs

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