Concept

Coloration des arêtes d'un graphe

Publications associées (169)

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

Graphs that Admit Right Angle Crossing Drawings

Radoslav Fulek, Balázs Keszegh, Filip Moric

We consider right angle crossing (RAC) drawings of graphs in which the edges are represented by polygonal arcs and any two edges can cross only at a right angle. We show that if a graph with n vertices admits a RAC drawing with at most 1 bend or 2 bends pe ...

2010

k-Edge-Connectivity: Approximation and LP Relaxation

David Pritchard

This paper's focus is the following family of problems, denoted k-ECSS, where k denotes a positive integer: given a graph (V, E) and costs for each edge, find a minimum-cost subset F of E such that (V, F) is k-edge-connected. For k=1 it is the spanning tre ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2010

A Computational Approach to Conway's Thrackle Conjecture

János Pach, Radoslav Fulek

A drawing of a graph in the plane is called a thrackle if every pair of edges meets precisely once, either at a common vertex or at a proper crossing. Let t(n) denote the maximum number of edges that a thrackle of n vertices can have. According to a 40 yea ...

Springer2010

An Optimal Linear-Time Algorithm for Interprocedural Register Allocation in High Level Synthesis Using SSA Form

Paolo Ienne, Philip Brisk, Ajay Kumar Verma

An optimal linear-time algorithm for interprocedural register allocation in high level synthesis is presented. Historically, register allocation has been modeled as a graph coloring problem, which is nondeterministic polynomial time-complete in general; ho ...

2010

A separator theorem for string graphs and its applications

János Pach

A string graph is the intersection graph of a collection of continuous arcs in the plane. We show that any string graph with in edges can be separated into two parts of roughly equal size by the removal of O(m(3/4)root log m) vertices. This result is then ...

Cambridge University Press2010

Decomposition of Geometric Set Systems and Graphs

We study two decomposition problems in combinatorial geometry. The first part of the thesis deals with the decomposition of multiple coverings of the plane. We say that a planar set is cover-decomposable if there is a constant m such that any m-fold coveri ...

EPFL2010

Degree-constrained edge partitioning in graphs arising from discrete tomography

Dominique de Werra, Bernard Ries

Starting from the basic problem of reconstructing a 2-dimensional image given by its projections on two axes, one associates a model of edge coloring in a complete bipartite graph. The complexity of the case with k=3 colors is open. Variations and special ...

2009

Graph coloring with cardinality constraints on the neighborhoods

Dominique de Werra, Bernard Ries

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 ...

2009

2D-TUCKER Is PPAD-Complete

Tucker's lemma states that if we triangulate the unit disc centered at the origin and color the vertices with {1, 1,2, 2} in an antipodal way (if vertical bar z vertical bar = 1, then the sum of the colors of z and -z is zero), then there must be an edge F ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2009

A tutorial on the use of graph coloring for some problems in robotics

Dominique de Werra, Tinaz Ekim

We study the problem where a robot has to pick up items of different sizes which are stored along a corridor. A natural requirement is that the items have to be collected in decreasing order of their sizes. We deal with various systems according to the loc ...

2009