Minimum Cuts in Surface Graphs (Q5885599)

scientific article; zbMATH DE number 7672227

Language	Label	Description	Also known as
English	Minimum Cuts in Surface Graphs	scientific article; zbMATH DE number 7672227

Statements

instance of

scholarly article

0 references

title

Minimum Cuts in Surface Graphs (English)

0 references

0 references

0 references

0 references

0 references

SIAM Journal on Computing

0 references

publication date

4 April 2023

0 references

full work available at URL

https://arxiv.org/abs/1910.04278

0 references

zbMATH Keywords

minimum cuts

0 references

surface-embedded graphs

0 references

computational topology

0 references

homology

0 references

algorithms

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs

0 references

Q3056948

0 references

Recognizing weakly simple polygons

0 references

Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus

0 references

Spanning trees of dual graphs

0 references

Minimum cycle and homology bases of surface-embedded graphs

0 references

Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs

0 references

All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs

0 references

Q2934724

0 references

Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon

0 references

An O (n log n) algorithm for maximum st-flow in a directed planar graph

0 references

An O ( n log n ) algorithm for maximum st -flow in a directed planar graph

0 references

Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time

0 references

Many distances in planar graphs

0 references

Finding shortest contractible and shortest separating cycles in embedded graphs

0 references

Multiple-Source Shortest Paths in Embedded Graphs

0 references

Finding shortest non-trivial cycles in directed graphs on surfaces

0 references

Finding one tight cycle

0 references

Finding shortest non-separating and non-contractible cycles for topologically embedded graphs

0 references

Q5501344

0 references

Splitting (complicated) surfaces is hard

0 references

Flows in One-Crossing-Minor-Free Graphs

0 references

Minimum cuts and shortest homologous cycles

0 references

Homology Flows, Cohomology Cuts

0 references

Detecting Weakly Simple Polygons

0 references

Quantifying Homology Classes

0 references

Q5417733

0 references

Shortest Cut Graph of a Surface with Prescribed Vertex Set

0 references

Tightening non-simple paths and cycles on surfaces

0 references

Tightening Nonsimple Paths and Cycles on Surfaces

0 references

Optimal pants decompositions and shortest homotopic cycles on an orientable surface

0 references

Q2934606

0 references

Optimal homologous cycles, total unimodularity, and linear programming

0 references

Q3549731

0 references

Graphs on Surfaces

0 references

Subgraph Isomorphism in Planar Graphs and Related Problems

0 references

Diameter and treewidth in minor-closed graph families

0 references

Q4471349

0 references

Q5417668

0 references

Shortest non-trivial cycles in directed surface graphs

0 references

Holiest minimum-cost paths and flows in surface graphs

0 references

Q5743478

0 references

Q5365107

0 references

Q2921775

0 references

Planar graphs, negative weight edges, shortest paths, and near linear time

0 references

Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth

0 references

Maximal Flow Through a Network

0 references

Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs

0 references

Fast Algorithms for Shortest Paths in Planar Graphs, with Applications

0 references

Beyond the flow decomposition barrier

0 references

A new approach to the maximum-flow problem

0 references

Q4829022

0 references

Computational topology and the Unique Games Conjecture

0 references

Isomorphism testing for embeddable graphs through definability

0 references

Q2732568

0 references

Characterizing multiterminal flow networks and computing flows in networks of small treewidth

0 references

A Faster Algorithm for Finding the Minimum Cut in a Directed Graph

0 references

An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks

0 references

Q4819371

0 references

Local Flow Partitioning for Faster Edge Connectivity

0 references

Faster shortest-path algorithms for planar graphs

0 references

Q2934672

0 references

Q4148000

0 references

Maximum Flow in Planar Networks

0 references

Improved algorithms for min cut and max flow in undirected planar graphs

0 references

Q4008192

0 references

Q3113677

0 references

Minimum cuts in near-linear time

0 references

Deterministic Edge Connectivity in Near-Linear Time

0 references

Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time

0 references

Using generic programming for designing a data structure for polyhedral surfaces

0 references

Shortest paths in directed planar graphs with negative lengths

0 references

Q2921664

0 references

Q3601569

0 references

Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time

0 references

Graphs on surfaces and their applications. Appendix by Don B. Zagier

0 references

Graph-encoded maps

0 references

Generalized Nested Dissection

0 references

Q3435477

0 references

Easy and difficult objective functions for max cut

0 references

Flow in Planar Graphs with Multiple Sources and Sinks

0 references

Q2726740

0 references

Q4607913

0 references

Computing Edge-Connectivity in Multigraphs and Capacitated Graphs

0 references

Max flows in O(nm) time, or better

0 references

Fast and Efficient Parallel Solution of Sparse Linear Systems

0 references

Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time

0 references

The cycle space of an embedded graph

0 references

Q4773723

0 references

SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEM

0 references

Combinatorial optimization. Polyhedra and efficiency (3 volumes)

0 references

On the History of Combinatorial Optimization (Till 1960)

0 references

Q3135833

0 references

A simple min-cut algorithm

0 references

Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation

0 references

Maximum $(s,t)$-flows in planar networks in $\mathcal O(|V| \log |V|)$ time

0 references

Planar Graphs

0 references

Identifiers

DOI

10.1137/19M1291820

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5885599