Computing sharp bounds for hard clustering problems on trees

DOI10.1016/j.dam.2008.03.032zbMath1169.05381OpenAlexW2063488705MaRDI QIDQ1028427

Maurizio Maravalle, Isabella Lari, Bruno Simeone

Publication date: 30 June 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.03.032

zbMATH Keywords

computational complexitylinear programmingheuristicsinteger programmingtreesdistribution networksdistrictingclustering problemsbiological taxonomycomuunication networkscontiguity-constrained clusteringdata base pagingoptimal tree partitioning problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On finding connected balanced partitions of trees, On the complexity of isoperimetric problems on trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clustering with relational constraint
• Clustering on trees
• Maximum split clustering under connectivity constraints
• A new algorithm for minimizing convex functions over convex sets
• Cluster Analysis: An Application of Lagrangian Relaxation
• Contextual Template Matching: A Distance Measure for Patterns with Hierarchically Dependent Features
• Conditional Clustering
• Bicriterion Cluster Analysis
• Maximal Closure of a Graph and Applications to Combinatorial Problems
• On constrained optimization by adjoint based quasi-Newton methods
• Generalized Bundle Methods
• Cluster Analysis and Mathematical Programming