The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al.
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.
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 ...
In the Information Embedding Problem one is given a piece of data which can be altered only conditionally, for example only at certain places. One is then asked to embed an arbitrary message into the data by only applying admissible changes to the data. Th ...
During the past decade, a number of different studies have identified several peculiar properties of networks that arise from a diverse universe, ranging from social to computer networks. A recently observed feature is known as network densification, which ...
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 study online partitioning of posets from a graph theoretical point of view, which is coloring and cocoloring in comparability graphs. For the coloring problem, we analyse the First-Fit algorithm and show a ratio of O(n); furthermore, we devise ...
In this paper, we propose a new method for the motion planning problem of rigid object dexterous manipulation with a robotic multi-fingered hand, under quasi-static movement assumption. This method computes both object and finger trajectories as well as th ...
Network tomography infers internal network characteristics by sending and collecting probe packets from the network edge. Traditional tomographic techniques for general topologies typically use a mesh of multicast trees and/or unicast paths to cover the en ...
In message-passing parallel applications, messages are not delivered in a strict order. The number of messages, their content and their destination may depend on the ordering of their delivery. Nevertheless, for most applications, the computation results s ...
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})
Wireless Sensor Networks (WSN) comprise a fast developing research area with a vast spectrum of applications. A WSN design is influenced by many factors such as transmission errors, network topology and power consumption. Consequently, developing a WSN app ...
