Approximating Maximum Subgraphs without Short Cycles

DOI10.1007/978-3-540-85363-3_10MaRDI QIDQ5900473zbMATH OpenOpenAlexFDO

Authors Guy Kortsarz, Michael Langberg, Zeev Nutov

Publication date 27 November 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85363-3_10

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Approximating maximum subgraphs without short cycles
• Approximation algorithms for cycle packing problems
• Cycle transversals in bounded degree graphs
• Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
• Approximation algorithms and hardness results for cycle packing problems

Cited in

(13)

• Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
• An approximation algorithm for the maximum spectral subgraph problem
• New kernels for several problems on planar graphs
• On generating triangle-free graphs
• Cycle transversals in bounded degree graphs
• On the small cycle transversal of planar graphs
• Tight Bounds for the Maximum Acyclic Subgraph Problem
• The approximation of maximum subgraph problems
• Inapproximability of \(H\)-transversal/packing
• Inapproximability of \(H\)-transversal/packing
• Cycle transversals in bounded degree graphs
• On the small cycle transversal of planar graphs
• Approximating maximum subgraphs without short cycles

This page was built for publication: Approximating Maximum Subgraphs without Short Cycles

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