The clustering matroid and the optimal clustering tree

DOI10.1007/s10107-003-0410-xzbMath1160.90638MaRDI QIDQ1424305

D. Massart

Publication date: 11 March 2004

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-003-0410-x

zbMATH Keywords

polyhedra; combinatorial optimization; hypergraphs; matroids; primal-dual algorithms; clustering spanning trees; polynomial graph algorithms

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

52B40: Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

05B05: Combinatorial aspects of block designs

90C27: Combinatorial optimization

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Approximation Algorithms for Not Necessarily Disjoint Clustered TSP, Unnamed Item, Short Plane Supports for Spatial Hypergraphs, Online and Approximate Network Construction from Bounded Connectivity Constraints, On the approximability and hardness of minimum topic connected overlay and its special instances, Path-based supports for hypergraphs, Equal-need sharing of a network under connectivity constraints, Complexity dichotomies for the \textsc{Minimum} \(\mathcal{F}\)-\textsc{Overlay} problem, Short plane supports for spatial hypergraphs, Network construction with subgraph connectivity constraints, The complete optimal stars-clustering-tree problem, Vertices removal for feasibility of clustered spanning trees, Online and approximate network construction from bounded connectivity constraints, Twins in Subdivision Drawings of Hypergraphs, Path-Based Supports for Hypergraphs, Blocks of Hypergraphs