Two real-life applications of graph partitioning
Închide
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

Two real-life applications of graph partitioning


Pag. 19-20

Buzatu Radu
 
Moldova State University
 
Disponibil în IBN: 29 iunie 2021


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].