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 algorithmstransversalscycle-transversals

Mathematics Subject Classification ID

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

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)

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