Articolul precedent |
Articolul urmator |
281 5 |
Ultima descărcare din IBN: 2023-12-05 10:21 |
SM ISO690:2012 BUZATU, Radu. Two real-life applications of graph partitioning. In: Mathematics and IT: Research and Education, 1-3 iulie 2021, Chişinău. Chișinău, Republica Moldova: 2021, pp. 19-20. |
EXPORT metadate: Google Scholar Crossref CERIF DataCite Dublin Core |
Mathematics and IT: Research and Education 2021 | |||||
Conferința "Mathematics and IT: Research and Education " Chişinău, Moldova, 1-3 iulie 2021 | |||||
|
|||||
Pag. 19-20 | |||||
|
|||||
Descarcă PDF | |||||
Rezumat | |||||
Graph partitioning is a widely researched topic that has extensive applications in many areas, including scientific computing, data mining, VLSI design, image analysis, air traffic control, etc. Let G = (V;E) be a simple graph and Pk = fV1; V2; :::; Vkg a set of subsets of V . Pk is said to be a partition of G if: 1. no element of Pk is empty: 8i 2 f1; 2; ::; kg; Vi 6= ?; 2. the elements of Pk are pairwise disjoint: 8(i; j) 2 f1; 2; ::; kg2; i 6= j, Vi \ Vj = ?; 3. the union of all the elements of Pk is equal to V : Sk i=1 Vi = V . The elements Vi of Pk are called the parts of the partition. The number k is called the cardinality of the partition, or the number of parts of the partition. Usually, graph partitioning problems seek to optimize some objective functions and satisfy various constraints imposed on the parts of the partition. Such optimization graph partitioning problems typically fall under the category of NP-hard problems. As a result, solutions to these problems are generally obtained using heuristics and approximation algorithms.We present two examples of real-life applications of graph partitioning problems, where some special heuristic were used to make them tractable: optimization of administrative-territorial structure [1, 2], organization of electoral districts of a State [3]. |
|||||
|