Publication

Generalized vertex coloring problems using split graphs

Publications associées (195)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

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

Scheduling multicasts on unit-capacity trees and meshes

Monika Henzinger

This paper studies the multicast routing and admission control problem on unit-capacity tree and mesh topologies in the throughput model. The problem is a generalization of the edge-disjoint paths problem and is NP-hard both on trees and meshes. We study b ...

2003

Automatic failure-path inference: a generic introspection technique for Internet applications

George Candea

Automatic failure-path inference (AFPI) is an application-generic, automatic technique for dynamically discovering the failure dependency graphs of componentized Internet applications. AFPI's first phase is invasive, and relies on controlled fault injectio ...

2003

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

Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron

Thomas Liebling, François Margot

In this paper, we investigate the applicability of backtrack technique to solve the vertex enumeration problem and the face enumeration problem for a convex polyhedron given by a system of linear inequalities. We show that there is a linear-time backtrack ...

1997

Finding all common bases in two matroids

In this paper, we present an algorithm for finding all common bases in two matroids. Our algorithm lists all common bases by using pivot operations in such a way that each basis appears exactly once. The time complexity of the algorithm is O(n(n^2+t)§) whe ...

1995

Some complexity results about threshold graphs

François Margot

The problem of determining whether a graph G contains a threshold subgraph containing at least h edges is shown to be NP-complete if h is part of the input as the problems of minimum threshold completion, weighted 2-threshold partition and weighted 2-thres ...

1994

Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron

Thomas Liebling, François Margot

In this paper, we investigate the applicability of backtrack technique for solving the vertex enumeration problem and the face enumeration problem for a convex polyhedron given by a system of linear inequalities. We show that there is a linear-time backtra ...

1994

Finding all the perfect matchings in bipartite graphs

This paper describes an algorithm for finding all the perfect matchings in a bipartite graph. By using the binary partitioning method, our algorithm requires O(c(n+m)+n^2.5) computational effort and O(nm) memmory storage, (where n denotes the number of ver ...

1994

The poset scheduling problem

Thomas Liebling, François Margot

The poser scheduling problem has been shown to be NP-complete in the general case but in P for a special case by Chang and Edmonds. In this paper, we extend the class of polynomially solvable cases and give some polyhedral characterizations. ...

1989