Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Concept

List edge-coloring

Publications associées (27)

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

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

Optimistic chordal coloring: a coalescing heuristic for SSA form programs

Paolo Ienne, Philip Brisk, Ajay Kumar Verma

The interference graph for a procedure in Static Single Assignment (SSA) Form is chordal. Since the k-colorability problem can be solved in polynomial-time for chordal graphs, this result has generated interest in SSA-based heuristics for spilling and coal ...

Springer US2009

Variable space search for graph coloring

Nicolas Zufferey

Let G = (V, E) be a graph with vertex set V and edge set E. The k-coloring problem is to assign a color (a number chosen in {1, ..., k}) to each vertex of G so that no edge has both endpoints with the same color. We propose a new local search methodology, ...

2008

On two coloring problems in mixed graphs

Dominique de Werra, Bernard Ries

We are interested in coloring the vertices of a mixed graph, i.e., a graph containing edges and arcs. We consider two different coloring problems: in the first one we want adjacent vertices to have different colors and the tail of an arc to get a color str ...

2008

Coloring some classes of mixed graphs

Bernard Ries

We consider the coloring problem for mixed graphs, that is, for graphs containing edges and arcs. A mixed coloring

c

is a coloring such that for every edge

[x_{i},x_{j}]

c(x_{i})\neq c(x_{j})

and for every arc

(x_{p},x_{q})

, $c(x_{p})

2007

Publications associées (27)

c

is a coloring such that for every edge

[x_{i},x_{j}]

c(x_{i})\neq c(x_{j})

and for every arc

(x_{p},x_{q})

, $c(x_{p})

2007