Search

We consider the Steiner k-cut problem which generalizes both the k-cut problem and the multiway cut problem. The Steiner k-cut problem is defined as follows. Given an edge-weighted undirected graph G = (V,E), a subset of vertices X ⊆ V called terminals, and an integer k ≥ ∣X∣, the objective is to find a minimum weight set of edges whose removal results in k disconnected components, each of which contains at least one terminal. We give two approximation algorithms for the problem: a greedy (2 - ... )-approximation based on Gomory-Hu trees, and a (2 - ... )- approximation based on rounding a linear program. We use the insight from the rounding to develop an exact bidirected formulation for the global minimum cut problem (the k-cut problem with k = 2). [ABSTRACT FROM AUTHOR]

We develop an algorithm framework for isomorph-free exhaustive generation of designs admitting a group of automorphisms from a prescribed collection of pairwise nonconjugate groups, where each prescribed group has a large index relative to its normalizer in the isomorphism-inducing group. We demonstrate the practicality of the framework by producing a complete classification of the Steiner triple systems of order $21$ admitting a nontrivial automorphism group. The number of such pairwise nonisomorphic designs is $62336617$, where $958$ of the designs are anti-Pasch. We also develop consistency checking methodology for gaining confidence in the correct operation of the algorithm implementation. [ABSTRACT FROM AUTHOR]