Approximating maximum subgraphs without short cycles

DOI10.1137/09074944XMaRDI QIDQ5894186zbMATH OpenFDO

Authors Guy Kortsarz, Michael Langberg, Zeev Nutov

Publication date 15 March 2011

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/09074944X

zbMATH Keywords

approximationcycles of length \(k\)girthLPpacking

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Approximation algorithms (68W25)

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

(10)

• Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
• An approximation algorithm for the maximum spectral subgraph problem
• Kernelization for cycle transversal problems
• Tight Bounds for the Maximum Acyclic Subgraph Problem
• The approximation of maximum subgraph problems
• Inapproximability of \(H\)-transversal/packing
• Cycle transversals in bounded degree graphs
• Approximating Maximum Subgraphs without Short Cycles
• Packing and Covering a Given Directed Graph in a Directed Graph
• Fitting metrics and ultrametrics with minimum disagreements

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 Q5894186)