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.
We study complexity issues related to some coloring problems in grids: we examine in particular the case of List coloring, of Precoloring extension and of (p, q)-List coloring, the case of List coloring in bipartite graphs where lists in the first part of ...
In this paper, we study the performance of IPOP-saACM-ES, recently proposed self-adaptive surrogate-assisted Covariance Matrix Adaptation Evolution Strategy. The algorithm was tested using restarts till a total number of function evaluations of 10^6D was r ...
In the context of international sea-freight container transport, we study an integrated decision problem arising in container terminal management. We consider the integration of the Berth Allocation Problem (BAP), which consists of assigning and scheduling ...
Graph matching is a generalization of the classic graph isomorphism problem. By using only their structures a graph-matching algorithm finds a map between the vertex sets of two similar graphs. This has applications in the de-anonymization of social and in ...
There is an increasing interest for the integration of supply-demand interactions in airline schedule planning models. We work with an itinerary-based fleet assignment model where an itinerary choice model is explicitly integrated. The choice model represe ...
Extensions and variations of the basic problem of graph coloring are introduced. The problem consists essentially in finding in a graph G a k-coloring, i.e., a partition V-1,...,V-k of the vertex set of G such that, for some specified neighborhood (N) over ...
In threshold graphs one may find weights for the vertices and a threshold value t such that for any subset S of vertices, the sum of the weights is at most the threshold t if and only if the set S is a stable (independent) set. In this note we ask a simila ...
We deal with some generalizations of the graph coloring problem on classes of perfect graphs. Namely we consider the μ-coloring problem (upper bounds for the color on each vertex), the precoloring extension problem (a subset of vertices colored beforehand) ...
In the context of international sea-freight container transport, we study an integrated decision problem arising in container terminal management. We consider the integration of the Berth Allocation Problem (BAP), which consists of assigning and scheduling ...
Given a geometric hypergraph (or a range-space) H=(V,E), a coloring of its vertices is said to be conflict-free if for every hyperedge S∈E there is at least one vertex in S whose color is distinct from the colors of all other vertices i ...
