Adaptive majority problems for restricted query graphs and for weighted sets
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.
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 ...
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 ...
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 ...
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 ...
We give a general proof of aging for trap models using the arcsine law for stable subordinators. This proof is based on abstract conditions on the potential theory of the underlying graph and on the randomness of the trapping landscape. We apply this proof ...
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 [xi,xj], c(xi)=c(xj) and for every arc (xp,xq), $c(x_{p})
We extend the connection graph stability method for complete synchronization, originally developed for symmetrically coupled networks, to the asymmetrical case. First, we study synchronization in asymmetrically connected networks with node balance, the pro ...
We introduce "derandomized" versions of the tensor product and the zig-zag product, extending the ideas in the derandomized squaring operation of Rozenman and Vadhan. These enable us to obtain graphs with smaller degrees than those obtained using their non ...
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 ...
