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.
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 ...
We consider a multicast configuration with two sources, and translate the network code design problem to vertex coloring of an appropriately defined graph. This observation enables to derive code design algorithms and alphabet size bounds, as well as estab ...
We present a type system for a language based on F-sub, which allows certain type annotations to be elided in actual programs. Local type inference determines types by a combination of type propagation and local constraint solving, rather than by global co ...
The common point between the different chapters of the present work is graph theory. We investigate some well known graph theory problems, and some which arise from more specific applications. In the first chapter, we deal with the maximum stable set probl ...
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 ...
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 ...
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 ...
Randomized stopping points form a convex set associated with the information structure that arises in the context of the optimal stopping problem for two-parameter processes. We study combinatorial properties of this structure when the underlying space is ...
Register allocation is an important component of most compilers, particularly those for RISC machines. The SPUR Lisp compiler uses a sophisticated, graph-coloring algorithm developed by Fredrick Chow [Chow84]. This paper describes the algorithm and the tec ...