scientific article; zbMATH DE number 7053355

zbMath1423.05168MaRDI QIDQ5743478

Jeff Erickson, Kyle Fox, Amir Nayyeri

Publication date: 10 May 2019

Full work available at URL: https://dl.acm.org/citation.cfm?id=2095219

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Minimum Cuts in Surface Graphs ⋮ Multicuts in planar and bounded-genus graphs with bounded number of terminals ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Counting and sampling minimum cuts in genus \(g\) graphs ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ Discrete systolic inequalities and decompositions of triangulated surfaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the shortest essential cycle
• Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
• Embeddings of graphs with no short noncontractible cycles
• Splitting (complicated) surfaces is hard
• Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
• Measuring and computing natural generators for homology groups
• Matching is as easy as matrix inversion
• Optimally cutting a surface into a disk
• Diameter and treewidth in minor-closed graph families
• Optimal homologous cycles, total unimodularity, and linear programming
• Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time
• Isomorphism testing for embeddable graphs through definability
• Maximal Flow Through a Network
• An O ( n log n ) algorithm for maximum st -flow in a directed planar graph
• The Two-Edge Connectivity Survivable Network Problem in Planar Graphs
• Optimal pants decompositions and shortest homotopic cycles on an orientable surface
• Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time
• Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon
• An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Maximum Flow in Planar Networks
• Generalized Nested Dissection
• Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Quantifying Homology Classes
• Homology flows, cohomology cuts
• Minimum cuts and shortest homologous cycles
• Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs
• Tightening Nonsimple Paths and Cycles on Surfaces
• The least spanning area of a knot and the optimal bounding chain problem
• Shortest non-trivial cycles in directed surface graphs
• Output-sensitive algorithm for the edge-width of an embedded graph
• Finding shortest non-trivial cycles in directed graphs on surfaces
• Improved algorithms for min cut and max flow in undirected planar graphs
• Minimum cuts in near-linear time
• Faster shortest-path algorithms for planar graphs

This page was built for publication: