Multiple-Source Shortest Paths in Embedded Graphs

Let $G$ be a directed graph with $n$ vertices and nonnegative weights in its directed edges, embedded on a surface of genus $g$, and let $f$ be an arbitrary face of $G$. We describe a randomized al...

• Publication year

  2012

• Venue

  SIAM journal on computing (Print)

• Publication date

  2012-02-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/120864271arXiv 1202.0314
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs

  2013cited by this paper
• THE GENERALIZED SIMPLEX METHOD FOR MINIMIZING A LINEAR FORM UNDER LINEAR INEQUALITY RESTRAINTS

  2012cited by this paper
• Shortest non-trivial cycles in directed surface graphs

  2011cited by this paper
• Faster Shortest Non-contractible Cycles in Directed Surface Graphs

  2011cited by this paper
• Minimum k-way cut of bounded size is fixed-parameter tractable

  2011cited by this paper
• Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs

  2011cited by this paper
• Computing replacement paths in surface embedded graphs

  2011cited by this paper
• Minimum cuts and shortest non-separating cycles via homology covers

  2011cited by this paper
• Min st-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time

  2010cited by this paper
• Computing the Shortest Essential Cycle

  2010cited by this paper
• Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation

  2009cited by this paper
• Optimal Embedding into Star Metrics

  2009cited by this paper
• Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs

  2009cited by this paper
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth

  2009cited by this paper
• Minimum Cycle Basis and All-Pairs Min Cut of a Planar Graph in Subquadratic Time

  2009cited by this paper
• Finding one tight cycle

  2008cited by this paper
• Exploiting Planarity for Network Flow and Connectivity Problems

  2008cited by this paper
• A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width

  2008cited by this paper
• SHORTEST PATH ALGORITThMS WITH AN APPLICATION TO CYCLIC STAFFING

  2008cited by this paper
• Multiple source shortest paths in a genus g graph

  2007cited by this paper
• Splitting (complicated) surfaces is hard

  2006cited by this paper
• Many Distances in Planar Graphs

  2006cited by this paper
• Tightening non-simple paths and cycles on surfaces

  2006cited by this paper
• An O (n log n) algorithm for maximum st-flow in a directed planar graph

  2006influential reference
• Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time

  2005cited by this paper
• On the History of Combinatorial Optimization (Till 1960)

  2005cited by this paper
• Self-adjusting top trees

  2005influential reference
• Multiple-source shortest paths in planar graphs

  2005influential reference
• Finding Shortest Non-Separating and Non-Contractible Cycles for Topologically Embedded Graphs

  2005influential reference
• Raccourcissement de courbes et décomposition de surfaces

  2003cited by this paper
• Optimally Cutting a Surface into a Disk

  2002influential reference
• Dynamic generators of topologically embedded graphs

  2002cited by this paper
• Graphs on Surfaces

  2001cited by this paper
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation

  1999cited by this paper
• Parametric and kinetic minimum spanning trees

  1998influential reference
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings

  1998cited by this paper
• Kinetic data structures: a state of the art report

  1998cited by this paper
• Dynamic trees as search trees via euler tours, applied to the network simplex algorithm

  1997cited by this paper
• Data structures for mobile data

  1997cited by this paper
• A Note on Approximating Graph Genus

  1997cited by this paper
• The All-Pairs Min Cut Problem and the Minimum Cycle Basis Problem on Planar Graphs

  1994influential reference
• Faster shortest-path algorithms for planar graphs

  1994cited by this paper
• Efficiency of the Primal Network Simplex Algorithm for the Minimum-Cost Circulation Problem

  1991cited by this paper
• Faster parametric shortest path and minimum-balance algorithms

  1991cited by this paper
• Use of dynamic trees in a network simplex algorithm for the maximum flow problem

  1991cited by this paper
• Geometry of the Gass-Saaty parametric cost LP algorithm

  1990cited by this paper
• Embeddings of graphs with no short noncontractible cycles

  1990cited by this paper
• Finding minimum-cost circulations by canceling negative cycles

  1989cited by this paper
• The Graph Genus Problem is NP-Complete

  1989cited by this paper
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications

  1987cited by this paper
• Matching is as easy as matrix inversion

  1987influential reference
• Making data structures persistent

  1986cited by this paper
• Fibonacci heaps and their uses in improved network optimization algorithms

  1984cited by this paper
• Parametric Combinatorial Computing and a Problem of Program Module Distribution

  1983cited by this paper
• A data structure for dynamic trees

  1981cited by this paper
• A Separator Theorem for Planar Graphs

  1977cited by this paper
• Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases

  1976cited by this paper
• A note on two problems in connexion with graphs

  1959cited by this paper
• NETWORK FLOW THEORY

  1956cited by this paper
• The computational algorithm for the parametric objective function

  1955cited by this paper
• Optimality and Degeneracy in Linear Programming

  1952cited by this paper
• Geometrie der Lage

  year unknowncited by this paper

• Algorithms for Distance Problems in Continuous Graphs

  2025cites this paper
• Faster Construction of a Planar Distance Oracle with Õ(1) Query Time

  2025cites this paper
• Distance Approximating Minors for Planar and Minor-Free Graphs

  2025cites this paper
• Testing whether a subgraph is convex or isometric

  2025influential citation
• Improved Distance (Sensitivity) Oracles with Subquadratic Space

  2024cites this paper
• Computing the second and third systoles of a combinatorial surface

  2024cites this paper
• A Survey on Concurrent Processing of Graph Analytical Queries: Systems and Algorithms

  2024cites this paper
• Computing shortest closed curves on non-orientable surfaces

  2024cites this paper
• Multi-Task Processing in Vertex-Centric Graph Systems: Evaluations and Insights

  2023cites this paper
• Fault-Tolerant ST-Diameter Oracles

  2023cites this paper
• 13 Multiple-Source Shortest Paths 13 . 1 Problem Statement

  2023cites this paper
• 13 Multiple-Source Shortest Paths 13 . 1 Problem Statement

  2023cites this paper
• Approximate Distance Sensitivity Oracles in Subquadratic Space

  2023cites this paper
• VC Set Systems in Minor-free (Di)Graphs and Applications

  2023cites this paper
• Dense or Sparse : Elastic SPMM Implementation for Optimal Big-Data Processing

  2023cites this paper
• Algorithms for Length Spectra of Combinatorial Tori

  2023cites this paper
• Almost Optimal Exact Distance Oracles for Planar Graphs

  2023influential citation
• Reconfiguration of Spanning Trees with Degree Constraints or Diameter Constraints

  2022cites this paper
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs

  2022cites this paper
• Fault-Tolerant Distance Labeling for Planar Graphs

  2021cites this paper
• A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs

  2021cites this paper
• Bavarian: Betweenness Centrality Approximation with Variance-Aware Rademacher Averages

  2021cites this paper
• An Almost Optimal Edit Distance Oracle

  2021cites this paper
• Continuously monitoring alternative shortest paths on road networks

  2020cites this paper
• Comparative Evaluation of Path Finding in All Pair Shortest Path Problem for Airline Network

  2020cites this paper
• Topology of Combinatorial Graphs

  2020cites this paper
• Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs

  2020cites this paper
• Notes on Graph Product Structure Theory

  2020cites this paper
• Data structures and dynamic algorithms for planar graphs

  2019cites this paper
• A Strongly Polynomial Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs

  2019cites this paper
• Min-Cost Flow in Unit-Capacity Planar Graphs

  2019cites this paper
• Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable

  2019cites this paper
• Minimum Cuts in Surface Graphs

  2019influential citation
• Finding a Shortest Non-Zero Path in Group-Labeled Graphs

  2019cites this paper
• The Interdisciplinary Center, Herzlia

  2019influential citation
• Exact Distance Oracles for Planar Graphs with Failing Vertices

  2018cites this paper
• On Almost Monge All Scores Matrices

  2018cites this paper
• Dynamic all scores matrices for LCS score

  2018cites this paper
• Almost optimal distance oracles for planar graphs

  2018cites this paper
• Holiest minimum-cost paths and flows in surface graphs

  2018cites this paper
• Topologically Trivial Closed Walks in Directed Surface Graphs

  2018cites this paper
• Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic Õ(n5/3) Time

  2017influential citation
• Computational topology of graphs on surfaces

  2017cites this paper
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic $\tilde{O}(n^{5/3})$ time

  2017cites this paper
• Minimum Weight Bases

  2017cites this paper
• Minimum Genus and Maximum Planar Subgraph: Exact Algorithms and General Limits of Approximation Algorithms

  2017cites this paper
• Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs

  2017influential citation
• Submatrix Maximum Queries in Monge Matrices and Partial Monge Matrices, and Their Applications

  2017cites this paper
• Voronoi diagrams on planar graphs , and computing the diameter in deterministic Õ ( n 5 / 3 ) time Pawe

  2017cites this paper
• Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths

  2017cites this paper
• Better Tradeoffs for Exact Distance Oracles in Planar Graphs

  2017cites this paper
• A Practical Method for the Minimum Genus of a Graph: Models and Experiments

  2016cites this paper
• iBFS: Concurrent Breadth-First Search on GPUs

  2016cites this paper
• 32nd International Symposium on Computational Geometry, SoCG 2016, Boston, MA, USA, June 14-18, 2016

  2016cites this paper
• Minimum cycle and homology bases of surface-embedded graphs

  2016influential citation
• Fully dynamic all-pairs shortest paths with worst-case update-time revisited

  2016cites this paper
• Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces

  2015cites this paper
• Minimum Cut of Directed Planar Graphs in O(n log log n) Time

  2015influential citation
• Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces

  2014cites this paper
• Computing the Stretch of an Embedded Graph

  2014cites this paper
• Faster shortest paths in dense distance graphs, with applications

  2014cites this paper
• Shortest-path queries in static networks

  2014cites this paper
• Solving the Content Routing Problem with Coupled Constraint Oriented Programs

  2014cites this paper
• Toward Practical Planar Graph Algorithms

  2014influential citation
• Fast algorithms for surface embedded graphs via homology

  2013cites this paper
• Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs

  2013influential citation
• Combinatorial Optimization of Cycles and Bases

  2012cites this paper
• Combinatorial optimization on embedded curves

  2012cites this paper
• Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time

  2011cites this paper
• Shortest non-trivial cycles in directed surface graphs

  2011cites this paper
• Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs

  2011cites this paper
• Computing replacement paths in surface embedded graphs

  2011cites this paper
• Faster Shortest Non-contractible Cycles in Directed Surface Graphs

  2011cites this paper
• Minimum cuts and shortest non-separating cycles via homology covers

  2011cites this paper
• Finding shortest non-trivial cycles in directed graphs on surfaces

  2010cites this paper