scientific article; zbMATH DE number 6469225

zbMATH Open1318.05073MaRDI QIDQ5501344FDOQ5501344

Authors: Parinya Chalermsook, Jittat Fakcharoenphol, Danupon Nanongkai 

Publication date: 3 August 2015

Title of this publication is not available (Why is that?)

Recommendations

• Deterministic global minimum cut of a simple graph in near-linear time
• Deterministic mincut in almost-linear time
• Minimum Cuts of Simple Graphs in Almost Always Linear Time
• Polynomial-time approximation scheme for minimum \(k\)-cut in planar and minor-free graphs
• scientific article; zbMATH DE number 7759280
• Min \(st\)-cut oracle for planar graphs with near-linear preprocessing time
• Min-cuts and shortest cycles in planar graphs in \(O(n \log\log n)\) time
• scientific article; zbMATH DE number 6850341
• A Deterministic Algorithm for Finding All Minimum k‐Way Cuts
• Solving minimum K-cardinality cut problems in planar graphs

Mathematics Subject Classification ID

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

Cited In (24)

• Efficient algorithms for \(k\)-terminal cuts on planar graphs
• Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
• Faster shortest paths in dense distance graphs, with applications
• Title not available (Why is that?)
• Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths
• Title not available (Why is that?)
• Planar graphs, negative weight edges, shortest paths, and near linear time
• On the negative cost girth problem in planar networks
• Counting and sampling minimum cuts in genus \(g\) graphs
• A fixed-parameter algorithm for the Max-Cut problem on embedded 1-planar graphs
• A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
• Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time
• Minimum Cuts in Surface Graphs
• An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem
• Min-cuts and shortest cycles in planar graphs in \(O(n \log\log n)\) time
• Minimum \(s-t\) cut in undirected planar graphs when the source and the sink are close
• An optimal algorithm for the minimum edge cardinality cut surface problem
• Global minimum cuts in surface embedded graphs
• Counting Minimum (s,t)-Cuts in Weighted Planar Graphs in Polynomial Time
• Exploiting planarity in separation routines for the symmetric traveling salesman problem
• A fast algorithm for minimum weight odd circuits and cuts in planar graphs
• A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs
• Contiguous minimum single-source-multi-sink cuts in weighted planar graphs
• Structured recursive separator decompositions for planar graphs in linear time

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5501344)