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, 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, Network construction with subgraph connectivity constraints, The complete optimal stars-clustering-tree problem, Twins in Subdivision Drawings of Hypergraphs, Path-Based Supports for Hypergraphs, Blocks of Hypergraphs