Generalized above guarantee vertex cover and r-partization

DOI10.1007/978-3-642-28076-4_5MaRDI QIDQ2889897zbMATH OpenOpenAlexFDO

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

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)

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

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)