Concept

Perfect graph

Related publications (96)

Suboptimal colorings and solution of large chromatic scheduling problems

Graph Coloring is a very active field of research in graph theory as well as in the domain of the design of efficient heuristics to solve problems which, due to their computational complexity, cannot be solved exactly (no guarantee that an optimal solution ...

EPFL2005

On the stable set polytope of claw-free graphs

Gautier Stauffer

In this thesis we focus our attention on the stable set polytope of claw-free graphs. This problem has been open for many years and albeit all the efforts engaged during those last three years, it is still open. This does not mean that no progress has been ...

EPFL2005

Circular Ones Matrices and the Stable set Polytopes of Quasi-Line Graphs

Friedrich Eisenbrand, Gautier Stauffer

It is a long standing open problem to find an explicit description of the stable set polytope of claw-free graphs. Yet more than 20 years after the discovery of a polynomial algorithm for the maximum stable set problem for claw-free graphs, there is even n ...

2005

Circular Ones Matrices and the Stable Set Polytope of Quasi-Line Graphs

Friedrich Eisenbrand, Gautier Stauffer

2004

On non-rank facets of the stable set polytope of claw-free graphs and circulant graphs

Thomas Liebling, Gautier Stauffer

We deal with non-rank facets of the stable set polytope of claw-free graphs. We extend results of Giles and Trotter [7] by (i) showing that for any nonnegative integer a there exists a circulant graph whose stable set polytope has a facet-inducing inequali ...

Springer-Verlag2004

on Non-Rank Facets of the Stable Set Polytope of Claw-Free Graphs and Circulant Graphs

Thomas Liebling, Gautier Stauffer

We deal with non-rank facets of the stable set polytope of claw-free graphs. We extend results of Gilles and Trotter (7) by (i) showing that for any nonnegative integer a there exists a circulant graph whose stable set polytope has a facet-inducing inequal ...

2003

Event Systems : How to Have Your Cake and Eat It Too

Rachid Guerraoui, Sidath Handurukande, Patrick Eugster

This paper addresses the fundamental tradeoffs in event systems between scalability (of event filtering, routing, and delivery mechanisms), expressiveness (when describing interests in events), and event safety (ensuring encapsulation and type-safe interac ...

2002

Bethe approximation for self-interacting lattice trees

Paolo De Los Rios

In this paper we develop a Bethe approximation, based on the cluster variation method, which is apt to study lattice models of branched polymers. We show that the method is extremely accurate in cases where exact results are known as, for instance, in the ...

EDP Sciences2001

Design of capacity-approaching irregular low-density parity-check codes

Rüdiger Urbanke, Mohammad Amin Shokrollahi

We design low-density parity-check (LDPC) codes that perform at rates extremely close to the Shannon capacity. The codes are built from highly irregular bipartite graphs with carefully chosen degree patterns on both sides. Our theoretical analysis of the c ...

2001

The dual role of functional pseudo-prolines for the design of novel SH3 ligands

Patricia Durieux

Pseudo-proline building blocks exert a dual functionality in enhancing and stabilizing the relevant polyproline II (PPII) conformation and increasing and optimizing van der Waals contacts and hydrogen bonding to the receptor mols. thus modifying affinity a ...

2001

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.