The complete optimal stars-clustering-tree problem

DOI10.1016/J.DAM.2006.12.004MaRDI QIDQ2473041zbMATH OpenOpenAlexFDO

Authors Ephraim Korach, Michal Stern

Publication date 26 February 2008

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

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

zbMATH Keywords

clustering spanning treescombinatorial optimizationhypergraphsNP-hardnesspolynomial graph algorithmsstars

Mathematics Subject Classification ID

Communication networks in operations research (90B18) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• On the Optimal Stars Clustering Tree Problem
• An algorithmic framework for the exact solution of tree-star problems
• The clustering matroid and the optimal clustering tree
• The tree-star problem: a formulation and a branch-and-cut algorithm
• Almost optimal solutions to k-clustering problems
• Branch‐and‐cut algorithms for the ‐arborescence star problem
• The p-arborescence star problem: formulations and exact solution approaches
• Algorithms for solving the \(k\)-star hub problem for trees and series-parallel graphs
• On variants of the spanning star forest problem
• scientific article; zbMATH DE number 3984569

Cites work

• Algorithmic graph theory and perfect graphs
• Graph theory with applications
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2021404 (Why is no real title available?)
• On the Consecutive-Retrieval Problem
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The clustering matroid and the optimal clustering tree
• Topics in Intersection Graph Theory

Cited in

(10)

• The clustering matroid and the optimal clustering tree
• Network construction with subgraph connectivity constraints
• Vertices removal for feasibility of clustered spanning trees
• On the Optimal Stars Clustering Tree Problem
• On the approximability and hardness of minimum topic connected overlay and its special instances
• Approximation algorithms for not necessarily disjoint clustered TSP
• Network construction with ordered constraints
• Clustered spanning tree -- conditions for feasibility
• Equal-need sharing of a network under connectivity constraints
• On the complexity of community-aware network sparsification

This page was built for publication: The complete optimal stars-clustering-tree problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2473041)