Connectivity-preserving minimum separator in AT-free graphs

DOI10.1007/978-3-032-11835-6_23MaRDI QIDQ7294440zbMATH OpenFDO

Authors Batya Kenig

Publication date 10 July 2026

Full work available at URL https://doi.org/10.1007/978-3-032-11835-6_23

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A deterministic almost-linear time algorithm for minimum-cost flow
• Asteroidal Triple-Free Graphs
• Connecting Terminals and 2-Disjoint Connected Subgraphs
• Detecting induced minors in AT-free graphs
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Faster energy maximization for faster maximum flow
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
• Graph algorithms. Edited by Guy Even. With a foreword by Richard M. Karp
• Maximum flow and minimum-cost flow in almost-linear time
• Minimum cost flows, MDPs, and ℓ ₁ -regression in nearly linear time for dense instances
• On partitioning a graph into two connected subgraphs
• On the connectivity preserving minimum cut problem
• Partitioning graphs into connected parts
• Removing local extrema from imprecise terrains
• Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
• Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph
• The Induced Disjoint Paths Problem
• Theoretical and computational advances for network diversion
• Two-sets cut-uncut on planar graphs
• Unit capacity maxflow in almost \(O(m^{4/3})\) time

This page was built for publication: Connectivity-preserving minimum separator in AT-free graphs

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