Concept

Topological sorting

Related publications (32)

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.

k-Quasi-Planar Graphs

A topological graph is k-quasi-planar if it does not contain k pairwise crossing edges. A topological graph is simple if every pair of its edges intersect at most once (either at a vertex or at their intersection). In 1996, Pach, Shahrokhi. and Szegedy [16 ...

Springer-Verlag Berlin2012

Intersection Patterns of Edges in Topological Graphs

Radoslav Fulek

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 ...

EPFL2012

Ecohydrological Footprints

Samir Suweis

Ecohydrological footprints are defined as the response of ecosystem functions or services to changes in their hydrologic drivers. In this thesis, several diverse footprints are addressed: noise-driven effects on storage-discharge relations and catchment st ...

EPFL2011

Local Graph-based Distributed Control for Safe Highway Platooning

Alcherio Martinoli, Sven Adrian Gowal, Riccardo Falconi

Using graph theory, this paper investigates how a group of vehicles, endowed with local positioning capabilities (range and bearing to other vehicles), can keep a predefined formation. We propose a longitudinal and lateral controller that stabilizes a syst ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2010

Sorting signed permutations by inversions in O(nlogn) time

Bernard Moret, Yu Lin, Vaibhav Rajan, Krister Swenson

The study of genomic inversions (or reversals) has been a mainstay of computational genomics for nearly 20 years. After the initial breakthrough of Hannenhalli and Pevzner, who gave the first polynomial-time algorithm for sorting signed permutations by inv ...

2010

Agent-Based Routing in Queueing Systems

Olivier Gallay

Waiting time in any network is often a costly and hence a bad experience. Therefore, to avoid jamming regions becomes essential in the optimization of traffic flows. In this regard, the conception and the control of complex networks supporting flows of uni ...

EPFL2010

On Depth-bounded Message Passing Systems

Damien Zufferey

We explore the border between decidability and undecidability of verification problems related to message passing systems that admit unbounded creation of threads and name mobility. Inspired by use cases in real-life programs we introduce the notion of dep ...

2009

Feedback topology and XOR-dynamics in Boolean networks with varying input structure

Carlo Maffi

We analyze a model of fixed in-degree random Boolean networks in which the fraction of input-receiving nodes is controlled by the parameter gamma. We investigate analytically and numerically the dynamics of graphs under a parallel XOR updating scheme. This ...

2009

Interval propagation and search on directed acyclic graphs for numerical constraint solving

Xuan-Ha Vu

The fundamentals of interval analysis on directed acyclic graphs (DAGs) for global optimization and constraint propagation have recently been proposed in Schichl and Neumaier (J. Global Optim. 33, 541-562, 2005). For representing numerical problems, the au ...

Springer US2009

Phylogenetic networks: modeling, reconstructibility, and accuracy

Bernard Moret, Tandy Warnow

Phylogenetic networks model the evolutionary history of sets of organisms when events such as hybrid speciation and horizontal gene transfer occur. In spite of their widely acknowledged importance in evolutionary biology, phylogenetic networks have so far ...

2004