scientific article; zbMATH DE number 7053306

zbMath1422.68294MaRDI QIDQ5743427

MohammadHossein Bateni, Claire Mathieu, Mohammad Taghi Hajiaghayi, Philip N. Klein

Publication date: 10 May 2019

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

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)

Related Items (6)

A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs ⋮ Multicuts in planar and bounded-genus graphs with bounded number of terminals ⋮ Correlation clustering and two-edge-connected augmentation for planar graphs ⋮ An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple algorithm for multicuts in planar graphs with outer terminals
• The planar multiterminal cut problem
• Rounding algorithms for a geometric embedding of minimum multiway cut
• Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth
• A subset spanner for Planar graphs, with application to subset TSP
• A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
• Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon
• Send-and-Split Method for Minimum-Concave-Cost Network Flows
• Approximation algorithms for NP-complete problems on planar graphs
• The Complexity of Multiterminal Cuts
• Subgraph Isomorphism in Planar Graphs and Related Problems
• A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
• Finding minimum-quotient cuts in planar graphs
• A Deterministic Algorithm for Finding All Minimum k‐Way Cuts

This page was built for publication: