publication . Part of book or chapter of book . 2014

claw free t perfect graphs can be recognised in polynomial time

Henning Bruhn; Oliver Schaudt;
Open Access
  • Published: 17 May 2014
  • Publisher: Springer International Publishing
Abstract
A graph is called t-perfect if its stable set polytope is defined by non-negativity, edge and odd-cycle inequalities. We show that it can be decided in polynomial time whether a given claw-free graph is t-perfect.
Subjects
free text keywords: Claw, Independent set, Time complexity, Graph, Computer science, Polytope, Recognition algorithm, Discrete mathematics
Related Organizations
Download from
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue