Publications associées à Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes

Variations of coloring problems related to scheduling and discrete tomography

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

Bicolored matchings in some classes of graphs

Dominique de Werra, Bernard Ries

We consider the problem of finding in a graph a set

R

of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with

n

nodes on each side, we give sufficient conditions f ...

2007

Robust Routing for Dynamic Wireless Networks Based on Stable Embeddings

Matthias Grossglauser, Suhas Diggavi, Dominique Florian Tschopp, Jörg Widmer

Routing packets is a central function of multi-hop wireless networks. Traditionally, there have been two paradigms for routing, either based on the geographical coordinates of the nodes (geographic routing), or based on the connectivity graph (topology-bas ...

2007

MFACE: A Multicast Backbone-Assisted Face Traversal Algorithm for Arbitrary Planar Ad Hoc and Sensor Network Topologies

François Ingelrest

Face is a well-known localized routing protocol for ad hoc and sensor networks which guarantees delivery of the message as long as a path exists between the source and the destination. This is achieved by employing a left/right hand rule to route the messa ...

2007

Gossiping in a Multi-Channel Radio Network (An Oblivious Approach to Coping With Malicious Interference)

Rachid Guerraoui, Seth Gilbert

We study oblivious deterministic gossip algorithms for multi-channel radio networks with a malicious adversary. In a multi-channel network, each of the n processes in the system must choose, in each round, one of the c channels of the system on which to pa ...

Springer2007

Generalized vertex coloring problems using split graphs

Tinaz Ekim

Graph theory experienced a remarkable increase of interest among the scientific community during the last decades. The vertex coloring problem (Min Coloring) deserves a particular attention rince it has been able to capture a wide variety of applications. ...

EPFL2006

An introduction to treewidth

Bernard Ries, Daniela Bronner

The notion of treewidth has seen to be a powerful vehicle for many graph algorithmic studies. A lot of problems, which are in general

NP

-complete, can be solved in polynomial time for graphs with small treewidth. In the first part of this paper we presen ...

2006

(k,lambda)-colorings and universal graphs

Ivo Blöchliger, Daniela Bronner

We consider vertex k-colorings of an arbitrary simple, connected, and undirected graph G=(V,E) such that, for every vertex v, at most lambda different colors occur in the closed neighborhood of v. These colorings are called (k,lambda)-colorings. If a graph ...

2006

New polynomial-time algorithms for Camion bases

Antoine Musitelli

Let M be a finite set of vectors in Rn of cardinality m and H(M) = {{x ∈ Rn : cTx = 0} : c ∈ M} the central hyperplane arrangement represented by M. An independent subset of M of cardinality n is called a Camion basis, if it determines a simplex region in ...

2006

Expanding graphs, Ramanujan graphs, and 1-factor perturbations

Antoine Musitelli

We construct (k±1)-regular graphs which provide sequences of expanders by adding or substracting appropriate 1- factors from given sequences of k- regular graphs. We compute numerical examples in a few cases for which the given sequences are from the work ...

2006

Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes

Graph Chatbot

Chattez avec Graph Search

Variations of coloring problems related to scheduling and discrete tomography

Bicolored matchings in some classes of graphs

Robust Routing for Dynamic Wireless Networks Based on Stable Embeddings

MFACE: A Multicast Backbone-Assisted Face Traversal Algorithm for Arbitrary Planar Ad Hoc and Sensor Network Topologies

Gossiping in a Multi-Channel Radio Network (An Oblivious Approach to Coping With Malicious Interference)

Generalized vertex coloring problems using split graphs

An introduction to treewidth

(k,lambda)-colorings and universal graphs

New polynomial-time algorithms for Camion bases

Expanding graphs, Ramanujan graphs, and 1-factor perturbations

Variations of coloring problems related to scheduling and discrete tomography

Bicolored matchings in some classes of graphs

Gossiping in a Multi-Channel Radio Network (An Oblivious Approach to Coping With Malicious Interference)

MFACE: A Multicast Backbone-Assisted Face Traversal Algorithm for Arbitrary Planar Ad Hoc and Sensor Network Topologies

Generalized vertex coloring problems using split graphs

Robust Routing for Dynamic Wireless Networks Based on Stable Embeddings

New polynomial-time algorithms for Camion bases

(k,lambda)-colorings and universal graphs

An introduction to treewidth

Expanding graphs, Ramanujan graphs, and 1-factor perturbations