To model the dynamics of discrete deterministic systems, we extend the Petri nets framework by a priority relation between conflicting transitions, which is encoded by orienting the edges of a transition conflict graph. The aim of this paper is to gain some insight into the structure of this conflict graph and to characterize a class of suitable orientations by an analysis in the context of hypergraph theory.
Clique family inequalities
,
form an intriguing class of valid inequalities
for the stable set polytopes of all graphs.
We prove firstly
that their
Chvátal-rank is at most , which
provides an alternative proof for the validity of clique family inequalities,
involving only standard rounding arguments.
Secondly, we strengthen the upper bound further and discuss consequences
regarding the Chvátal-rank of subclasses of claw-free graphs.
Perfect graphs constitute a well-studied graph class with a rich
structure, reflected by many characterizations with respect to
different concepts.
Perfect graphs are, for instance, precisely those graphs
where the stable set polytope STAB() coincides
with the fractional stable set polytope QSTAB().
For all imperfect graphs it holds that STAB() ⊂ QSTAB().
It is, therefore, natural to use the difference between the two polytopes
in order to decide how far an imperfect graph is away from...
Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs where the stable set polytope coincides with the fractional stable set polytope . For all imperfect graphs it holds that . It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph is away from being perfect. We discuss three...
Download Results (CSV)