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.
We study some variants of Conway’s thrackle conjecture. A tangle is a graph drawn in the plane such that its edges are represented by continuous arcs, and any two edges share precisely one point, which is either a common endpoint or an interior point at wh ...
Breadth First Search (BFS) is a widely used approach for sampling large graphs. However, it has been empirically observed that BFS sampling is biased toward high-degree nodes, which may strongly affect the measurement results. In this paper, we quantify an ...
Institute of Electrical and Electronics Engineers2011
In this thesis, we present new approximation algorithms as well as hardness of approximation results for NP-hard vehicle routing problems related to public transportation. We consider two different problem classes that also occur frequently in areas such a ...
The graph obtained from the integer grid Z x Z by the removal of all horizontal edges that do not belong to the x-axis is called a comb. In a random walk on a graph, whenever a walker is at a vertex v, in the next step it will visit one of the neighbors of ...
We present a distributed algorithm to compute the node search number in trees. This algorithm extends the centralized algorithm proposed by Ellis et al. (Inf. Comput. 113(1):50-79, 1994). It can be executed in an asynchronous environment, requires an overa ...
This paper introduces restart and nogood recording techniques in the domain of qualitative spatial and temporal reasoning. Nogoods and restarts can be applied orthogonally to usual methods for solving qualitative constraint satisfaction problems. In partic ...
The exponential number of possible subgraphs makes the problem of frequent subgraph mining a challenge. The set of maximal frequent subgraphs is much smaller to that of the set of frequent subgraphs providing ample scope for pruning. MARGIN is a maximal su ...
In our previous work we introduced the inverted MiniMag, a magnetic manipulation system capable of 5 degree-of-freedom (5-DOF) wireless control of micro- and nano structures. In this work, we implement a depth tracking algorithm to provide feedback on the ...
This thesis is devoted to crossing patterns of edges in topological graphs. We consider the following four problems: A thrackle is a graph drawn in the plane such that every pair of edges meet exactly once: either at a common endpoint or in a proper crossi ...
Genome-scale metabolic reconstructions (GEMs) are valuable resources for understanding and redesigning cellular networks as they encapsulate all the known biochemistry of the organisms from genes to proteins to their functions. Complexity of these large me ...
