Clustering with lower-bounded sizes. A general graph-theoretic framework

DOI10.1007/S00453-017-0374-5MaRDI QIDQ722539zbMATH OpenOpenAlexWikidataFDO

Authors Faisal N. Abu-Khzam, Cristina Bazgan, Katrin Casel, Henning Fernau

Publication date 26 July 2018

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-017-0374-5

zbMATH Keywords

anonymisationapproximation algorithmsclusteringcomputational complexity

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 6861937
• scientific article; zbMATH DE number 7746258
• Graph clustering with a constraint on cluster sizes
• A generalized minimum cost k-clustering
• Size-constrained graph partitioning polytopes

Cites work

• A Faster Deterministic Maximum Flow Algorithm
• A General Approximation Technique for Constrained Forest Problems
• A simplified NP-complete satisfiability problem
• Achieving anonymity via clustering
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Efficient algorithms for the 2-gathering problem
• Fast approximate PCPs
• scientific article; zbMATH DE number 6861937 (Why is no real title available?)
• Matching, Euler tours and the Chinese postman
• Max flows in O(nm) time, or better
• On min-max \(r\)-gatherings
• Optimization, approximation, and complexity classes
• Packing subgraphs in a graph
• Resolving the Complexity of Some Data Privacy Problems
• Terminal backup, 3D matching, and covering cubic graphs

Cited in

(5)

• Limitations on regularity lemmas for clustering graphs
• The complexity of the simultaneous cluster problem
• scientific article; zbMATH DE number 6861937 (Why is no real title available?)
• Resolving conflicts for lower-bounded clustering
• scientific article; zbMATH DE number 7746258 (Why is no real title available?)

This page was built for publication: Clustering with lower-bounded sizes. A general graph-theoretic framework

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