scientific article; zbMATH DE number 7651198

DOI10.4230/LIPICS.ESA.2020.59MaRDI QIDQ5874530zbMATH OpenFDO

Authors Alexander Noe, Christian Schulz, Darren Strash, Monika R. Henzinger

Publication date 7 February 2023

Full work available at URL https://arxiv.org/abs/2002.06948

zbMATH Keywords

graph algorithmminimum cutalgorithm engineeringbalanced cutglobal minimum cutcut enumerationlarge-scale graph analysis

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• scientific article; zbMATH DE number 7286685 (Why is no real title available?)
• A Fast Algorithm for Optimally Increasing the Edge Connectivity
• A clustering algorithm based on graph connectivity
• A fast algorithm for cactus representations of minimum cuts
• A new approach to the maximum-flow problem
• A new approach to the minimum cut problem
• A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem
• An Improved Min-Cut Algonthm for Partitioning VLSI Networks
• An algorithm for improving graph partitions
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• Canonical cactus representation for miminum cuts
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Counting almost minimum cutsets with reliability applications
• Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
• Depth-First Search and Linear Graph Algorithms
• Efficient algorithm for finding all minimal edge cuts of a nonoriented graph
• Engineering Kernelization for Maximum Cut
• Exact algorithms for cluster editing: Evaluation and experiments
• Exactly solving the maximum weight independent set problem on large real-world graphs
• Experimental and Efficient Algorithms
• Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
• Implementing an efficient minimum capacity cut algorithm
• Minimum cuts in near-linear time
• Most balanced minimum cuts
• Multi-Terminal Network Flows
• On the structure of all minimum cuts in a network and applications
• Positive-instance driven dynamic programming for treewidth
• Practical access to dynamic programming on tree decompositions
• Practical minimum cut algorithms
• Practical performance of efficient minimum cut algorithms
• Scalable kernelization for maximum independent sets
• Shared-Memory Branch-and-Reduce for Multiterminal Cuts
• Sparse matrices
• The University of Florida sparse matrix collection
• Turbo-charging dominating set with an FPT subroutine: further improvements and experimental analysis

Cited in

(4)

• The PACE 2022 parameterized algorithms and computational experiments challenge: directed feedback vertex set
• Applying a cut-based data reduction rule for weighted cluster editing in polynomial time
• Generalizing the all-pairs min cut problem
• Fully-dynamic min-cut

Describes a project that uses

Uses Software

• SparseMatrix

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 Q5874530)