Partitioning a graph into connected components with fixed centers and optimizing cost-based objective functions or equipartition criteria
| Autor: | Isabella Lari, Andrea Scozzari, Federica Ricca, Justo Puerto |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Connected component
Discrete mathematics tree partitioning 021103 operations research Optimization problem Computer Networks and Communications 0211 other engineering and technologies Graph partition p-centered partitions flat costs 0102 computer and information sciences 02 engineering and technology 01 natural sciences Vertex (geometry) Combinatorics Range criterion 010201 computation theory & mathematics Hardware and Architecture Partition (number theory) Time complexity Software Connectivity Information Systems Mathematics |
| Zdroj: | Networks. 67:69-81 |
| ISSN: | 0028-3045 |
| DOI: | 10.1002/net.21661 |
| Popis: | We consider a connected graph G with n vertices, p of which are centers, while the remaining ones are units. For each unit-center pair, there is a fixed assignment cost and for each vertex there is a nonnegative weight. In this article, we study the problem of partitioning G into p connected components such that each component contains exactly one center p-centered partition. We analyze different optimization problems of this type by defining different objective functions based on the assignment costs, or on the vertices' weights, or on both of them. For these problems, we show that they are NP-hard on very special classes of graphs, and for some of them we provide polynomial time algorithms when G is a tree. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 671, 69-81 2016 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text