Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Concept

Topological sorting

Related publications (21)

Analysis of a Canonical Labeling Algorithm for the Alignment of Correlated Erdős-Rényi Graphs

Matthias Grossglauser, Negar Kiyavash

Graph alignment in two correlated random graphs refers to the task of identifying the correspondence between vertex sets of the graphs. Recent results have characterized the exact information-theoretic threshold for graph alignment in correlated Erdös-Rény ...

Association for Computing Machinery (ACM)2019

Exact Synthesis of LTL Properties from Traces

Heinz Riener

We present an exact approach to synthesize temporal-logic formulas in linear temporal logic (LTL) from a set of given positive and negative example traces. Our approach uses topology structures, in particular partial DAGs, to partition the search space int ...

IEEE2019

Efficient Learning from Comparisons

Lucas Maystre

Humans are comparison machines: comparing and choosing an item among a set of alternatives (such as objects or concepts) is arguably one of the most natural ways for us to express our preferences and opinions. In many applications, the analysis of data con ...

EPFL2018

Many disjoint edges in topological graphs

Andres Jacinto Ruiz Vargas

A monotone cylindrical graph is a topological graph drawn on an open cylinder with an infinite vertical axis satisfying the condition that every vertical line intersects every edge at most once. It is called simple if any pair of its edges have at most one ...

Elsevier Science Bv2017

Disjoint edges in topological graphs and the tangled-thrackle conjecture

Andres Jacinto Ruiz Vargas

It is shown that fora constant t is an element of N, every simple topological graph on n vertices has 0(n) edges if the graph has no two sets of t edges such that every edge in one set is disjoint from all edges of the other set (i.e., the complement of th ...

Academic Press Ltd- Elsevier Science Ltd2016

Simple topological graphs : empty triangles and disjoint edges

Andres Jacinto Ruiz Vargas

This thesis is devoted to the understanding of topological graphs. We consider the following four problems: 1. A \emph{simple topological graph} is a graph drawn in the plane so that its edges are represented by continuous arcs with the property that any t ...

EPFL2016

Empty Triangles in Complete Topological Graphs

Andres Jacinto Ruiz Vargas

A simple topological graph is a graph drawn in the plane so that its edges are represented by continuous arcs with the property that any two of them meet at most once. Let be a complete simple topological graph on vertices. The three edges induced by any t ...

Springer2015

Improving Christofides' Algorithm for the s-t Path TSP

We present a deterministic (1+root 5/2)-approximation algorithm for the s-t path TSP for an arbitrary metric. Given a symmetric metric cost on n vertices including two prespecified endpoints, the problem is to find a shortest Hamiltonian path between the t ...

Assoc Computing Machinery2015

On grids in topological graphs

János Pach

A topological graph G is a graph drawn in the plane with vertices represented by points and edges represented by continuous arcs connecting the vertices. If every edge is drawn as a straight-line segment, then G is called a geometric graph. A k-grid in a t ...

Elsevier Science Bv2014

Approximation algorithms for regret minimization in vehicle routing problems

Adrian Aloysius Bock

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

EPFL2014

The Range of a Random Walk on a Comb

János Pach

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

Electronic Journal Of Combinatorics2013

Automated Reconstruction of Curvilinear Networks from 2D and 3D Imagery

Engin Türetken

Reconstructing complex curvilinear structures such as neural circuits, road networks, and blood vessels is a key challenge in many scientific and engineering fields. It has a broad range of applications, from the delineation of micrometer-sized neurons in ...

EPFL2013

Active topology inference using network coding

Christina Fragouli

Our goal, in this paper, is to infer the topology of a network when (i) we can send probes between sources and receivers at the edge of the network and (ii) intermediate nodes can perform simple network coding operations, i.e., additions. Our key intuition ...

2013

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 : Quantitative Response of Ecosystems to Changes in their Hydrological Drivers

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

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, Krister Swenson, Vaibhav Rajan

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

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

Related publications (21)