Publication

Disjoint homometric sets in graphs

Publications associées (61)

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

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

Parity-regular Steinhaus graphs

Maxime Augier

Steinhaus graphs on n vertices are certain simple graphs in bijective correspondence with binary {0,1}-sequences of length n-1. A conjecture of Dymacek in 1979 states that the only nontrivial regular Steinhaus graphs are those corresponding to the periodic ...

American Mathematical Society2008

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

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

On the Throughput Improvement due to Limited Complexity Processing at Relay Nodes

Christina Fragouli

We consider a source that transmits information to a receiver by routing it over a communication network represented by a graph and examine rate benefits that finite complexity processing at the intermediate nodes may offer. We show that there exist config ...

2005

A computational framework for the discovery of novel biotransformations

Vassily Hatzimanikatis

The large no. of chem. transformations involved in biochem. pathways and the even larger no. of enzymes that catalyze these transformations contribute to the complexity of biol. systems. Anal. of the available genome sequences, as well as results from prio ...

2003

Computing Vertex Connectivity: New Bounds from Old Techniques

Monika Henzinger

The vertex connectivity K of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the vertex connectivity and a corresponding separator. The time ...

2000

Improved data structures for fully dynamic biconnectivity

Monika Henzinger

We present fully dynamic algorithms for maintaining the biconnected components in general and plane graphs. A fully dynamic algorithm maintains a graph during a sequence of insertions and deletions of edges or isolated vertices. Let m be the number of edge ...

2000

Lower bounds for fully dynamic connectivity problems in graphs

Monika Henzinger

We prove lower bounds on the complexity of maintaining fully dynamic k-edge or k-vertex connectivity in plane graphs and in (k - 1)-vertex connected graphs. We show an amortized lower bound of 0(log n/k(log log n + log b)) per edge insertion, deletion, o ...

1998

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