Generalized above guarantee vertex cover and r-partization

DOI10.1007/978-3-642-28076-4_5zbMATH Open1350.68152OpenAlexW188882386MaRDI QIDQ2889897FDOQ2889897

Authors: R. Krithika, N. S. Narayanaswamy 

Publication date: 8 June 2012

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-28076-4_5

Recommendations

• Parameterized algorithms for \((r,l)\)-partization
• Parameterized algorithms on perfect graphs for deletion to \((r,\ell)\)-graphs
• Parameterized algorithms for deletion to \((r,\ell)\)-graphs
• Above guarantee parameterization for vertex cover on graphs with maximum degree 4
• LP can be a cure for parameterized problems

zbMATH Keywords

parameterized complexitysplit graphsperfect graphsodd cycle transversal\(r\)-partizationgeneralized above-guarantee vertex cover

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (2)

• Parameterized algorithms on perfect graphs for deletion to \((r,\ell)\)-graphs
• Parameterized algorithms for \((r,l)\)-partization

This page was built for publication: Generalized above guarantee vertex cover and \(r\)-partization

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