Conference
On the most imbalanced orientation of a graph
| العنوان: | On the most imbalanced orientation of a graph |
|---|---|
| المؤلفون: | Ben-Ameur, Walid, Glorieux, Antoine, Neto, José |
| المساهمون: | Méthodes et modèles pour les réseaux (METHODES-SAMOVAR), Services répartis, Architectures, MOdélisation, Validation, Administration des Réseaux (SAMOVAR), Institut Mines-Télécom Paris (IMT)-Télécom SudParis (TSP)-Institut Mines-Télécom Paris (IMT)-Télécom SudParis (TSP), Département Réseaux et Services Multimédia Mobiles (TSP - RS2M), Institut Mines-Télécom Paris (IMT)-Télécom SudParis (TSP), Centre National de la Recherche Scientifique (CNRS) |
| المصدر: | Proceedings COCOON 2015 : 21st International Conference on Computing and Combinatorics ; COCOON 2015 : 21st International Conference on Computing and Combinatorics ; https://hal.science/hal-01497825 ; COCOON 2015 : 21st International Conference on Computing and Combinatorics, Aug 2015, Beijing, China. pp.16 - 29, ⟨10.1007/978-3-319-21398-9_2⟩ |
| بيانات النشر: | HAL CCSD Springer international publishing |
| سنة النشر: | 2015 |
| مصطلحات موضوعية: | Orientation, Graph orientation, Imbalance, Combinatorial optimization, Complexity, NP-complete, Approximation algorithm, Mixed integer programming, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO]Computer Science [cs], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] |
| جغرافية الموضوع: | Beijing, China |
| الوصف: | International audience ; We study the problem of orienting the edges of a graph such that the minimum over all the vertices of the absolute difference between the outdegree and the indegree of a vertex is maximized. We call this minimum the imbalance of the orientation, i.e. the higher it gets, the more imbalanced the orientation is. We study this problem denoted by MaxIm. We first present different characterizations of the graphs for which the optimal objective value of MaxIm is zero. Next we show that it is generally NP-complete and cannot be approximated within a ratio of 1/2+ε for any constant ε>0 in polynomial time unless P=NP even if the minimum degree of the graph δ equals 2. Finally we describe a polynomial-time approximation algorithm whose ratio is equal to 1/2 for graphs where δ≡0[4] or δ≡1[4] and (1/2−1/δ) for general graphs. |
| نوع الوثيقة: | conference object |
| اللغة: | English |
| Relation: | hal-01497825; https://hal.science/hal-01497825; https://hal.science/hal-01497825v1/document; https://hal.science/hal-01497825v1/file/on_the_most_imbalanced_orientation_of_a_graph.pdf |
| DOI: | 10.1007/978-3-319-21398-9_2 |
| الاتاحة: | https://hal.science/hal-01497825 https://hal.science/hal-01497825v1/document https://hal.science/hal-01497825v1/file/on_the_most_imbalanced_orientation_of_a_graph.pdf https://doi.org/10.1007/978-3-319-21398-9_2 |
| Rights: | info:eu-repo/semantics/OpenAccess |
| رقم الانضمام: | edsbas.2EB343C |
| قاعدة البيانات: | BASE |
| DOI: | 10.1007/978-3-319-21398-9_2 |
|---|