Approximating Maximum Subgraphs without Short Cycles

DOI10.1137/09074944XzbMath1214.05057MaRDI QIDQ5894186

Michael Langberg, Guy Kortsarz, Zeev Nutov

Publication date: 15 March 2011

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

zbMATH Keywords

approximationpackinggirthLPcycles of length \(k\)

Mathematics Subject Classification ID

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

Related Items (4)

Inapproximability of $H$-Transversal/Packing ⋮ Packing and Covering a Given Directed Graph in a Directed Graph ⋮ Kernelization for cycle transversal problems ⋮ Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal

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