Concept

Eulerian path

Related publications (38)

Graph Chatbot

Chat with Graph Search

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.

Mixed graph edge coloring

Bernard Ries

We are interested in coloring the edges of a mixed graph. i.e., a graph containing unoriented and oriented edges. This problem is related to a communication problem in job-shop scheduling systems. In this paper we give general bounds oil the number of requ ...

Elsevier2009

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

Finding Hamiltonian circuits in quasi-adjoint graphs

Dominique de Werra, Benjamin Leroy-Beaulieu

This paper is motivated by a method used for DNA sequencing by hybridization presented in [Jacek Blazewicz, Marta Kasprzak, Computational complexity of isothernnic DNA sequencing by hybridization, Discrete Appl. Math. 154 (5) (2006) 718-7291. This paper pr ...

2008

Complexity of mixed graph coloring

Bernard Ries

In this note we consider two coloring problems in mixed graphs, i.e., graphs containing edges and arcs. We show that they are both

\mathcal{NP}

-complete in cubic planar bipartite graphs. This answers an open question from \cite{Ries2}. ...

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

Some coloring and walking problems in graphs

Benjamin Leroy-Beaulieu

Graph theory is an important topic in discrete mathematics. It is particularly interesting because it has a wide range of applications. Among the main problems in graph theory, we shall mention the following ones: graph coloring and the Hamiltonian circuit ...

EPFL2008

A new algorithm to simulate the dynamics of a glacier: theory and applications

Jacques Rappaz, Marco Picasso, Guillaume Jouvet, Heinz Blatter

We propose a novel Eulerian algorithm to compute the changes of a glacier geometry for given mass balances. The surface of a glacier is obtained by solving a transport equation for the volume of fluid (VOF). The surface mass balance is taken into account b ...

International Glaciological Society2008

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

Variations of coloring problems related to scheduling and discrete tomography

Bernard Ries

The graph coloring problem is one of the most famous problems in graph theory and has a large range of applications. It consists in coloring the vertices of an undirected graph with a given number of colors such that two adjacent vertices get different col ...

EPFL2007

On de Bruijn Routing in Distributed Hash Tables: There and Back Again

Karl Aberer, Anwitaman Datta, Sarunas Girdzijauskas

We show in this paper that de Bruijn networks, despite providing efficient search while using constant routing table size, as well as simplicity of the understanding and implementation of such networks, are unsuitable where key distribution will be uneven, ...

2004