scientific article; zbMATH DE number 2079379

MaRDI QIDQ4471338zbMATH OpenFDO

Authors Friedrich Eisenbrand, Stefan Funke, Naveen Garg, Jochen Könemann

Publication date 28 July 2004

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• scientific article; zbMATH DE number 3882470
• Algorithms for maximum independent sets
• Claw-free t-perfect graphs can be recognized in polynomial time
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• Finding independent sets in unions of perfect graphs

Cited in

(9)

• An SDP primal-dual algorithm for approximating the Lovász-theta function
• On the rational polytopes with Chvátal rank 1
• A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
• Complementation in T-perfect graphs
• Claw-free t-perfect graphs can be recognized in polynomial time
• Distributed approximate maximum matching in the CONGEST model
• \(t\)-perfection in \(P_5\)-free graphs
• Distributed approximation for \(f\)-matching
• A simple distributed algorithm for sparse fractional covering and packing problems

This page was built for publication:

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