Minimum Cuts in Surface Graphs (Q5885599)

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

Minimum Cuts in Surface Graphs

scientific article; zbMATH DE number 7672227

Language	Label	Description	Also known as
default for all languages	No label defined
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

Network flows. Theory, algorithms, and applications.

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

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

Hardness results for homology localization

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

Q3549731

0 references

Graphs on surfaces. Dualities, polynomials, and knots

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

Global minimum cuts in surface embedded graphs

0 references

Q5365107

0 references

Greedy optimal homotopy and homology generators

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

Topological graph theory.

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

Maximum $s$-$t$-flow with $k$ crossings in $O(k^3 n \log n)$ time

0 references

Q4148000

0 references

Maximum Flow in Planar Networks

0 references

Improved algorithms for \textsc{Min-cut} and \textsc{Max-flow} in undirected planar graphs

0 references

Q4008192

0 references

Minimum $s-t$ cut in undirected planar graphs when the source and the sink are close

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: a linear-space $O(n\log^{2} n)$-time algorithm

0 references

Multiple-source shortest paths in planar graphs

0 references

Q3601569

0 references

Min-cuts and shortest cycles in planar graphs in $O(n \log\log n)$ 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

Two linear time algorithms for MST on minor closed graph classes.

0 references

Easy and difficult objective functions for max cut

0 references

Flow in Planar Graphs with Multiple Sources and Sinks

0 references

Graphs on surfaces

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 Minimum Cuts in Surface Graphs