Evaluating topological ordering in directed acyclic graphs
<p class="p1">Directed acyclic graphs are often used to model situations and problems in real life. If we consider the topological ordering of the graph as a process of arranging the vertices in the best possible way considering the constraints caused by the direction of edges, then...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia
2021-10-01
|
| Series: | Electronic Journal of Graph Theory and Applications |
| Subjects: | |
| Online Access: | https://www.ejgta.org/index.php/ejgta/article/view/1212 |
| _version_ | 1818217403955281920 |
|---|---|
| author | Suzana Antunović Damir Vukičević |
| author_facet | Suzana Antunović Damir Vukičević |
| author_sort | Suzana Antunović |
| collection | DOAJ |
| description | <p class="p1">Directed acyclic graphs are often used to model situations and problems in real life. If we consider the topological ordering of the graph as a process of arranging the vertices in the best possible way considering the constraints caused by the direction of edges, then it makes sense to try to optimize this process by minimizing the distances between vertices in the ordering. For this purpose, we define measures based on distances between vertices in the topological ordering that allow us to construct a graph with optimal topological ordering regarding a specific measure thus minimizing the complexity of the system represented by the graph. We explore minimal and maximal values of the defined measures and comment on the topology of graphs for which maximal and minimal values are obtained. Potentially, the proved bounds could be used to benchmark existing algorithms, devise new approximation algorithms or branch and bound schemas for some scheduling problems that are usually of hard computational complexity.</p> |
| first_indexed | 2024-12-12T07:07:19Z |
| format | Article |
| id | doaj.art-ec87aa08ffa0451696819fb9c7b1c358 |
| institution | Directory Open Access Journal |
| issn | 2338-2287 |
| language | English |
| last_indexed | 2024-12-12T07:07:19Z |
| publishDate | 2021-10-01 |
| publisher | Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia |
| record_format | Article |
| series | Electronic Journal of Graph Theory and Applications |
| spelling | doaj.art-ec87aa08ffa0451696819fb9c7b1c3582022-12-22T00:33:42ZengIndonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), IndonesiaElectronic Journal of Graph Theory and Applications2338-22872021-10-019256758010.5614/ejgta.2021.9.2.25241Evaluating topological ordering in directed acyclic graphsSuzana Antunović0Damir Vukičević1Faculty of Civil Engineering, Architecture and Geodesy, University of Split, CroatiaFaculty of Science, University of Split, Croatia<p class="p1">Directed acyclic graphs are often used to model situations and problems in real life. If we consider the topological ordering of the graph as a process of arranging the vertices in the best possible way considering the constraints caused by the direction of edges, then it makes sense to try to optimize this process by minimizing the distances between vertices in the ordering. For this purpose, we define measures based on distances between vertices in the topological ordering that allow us to construct a graph with optimal topological ordering regarding a specific measure thus minimizing the complexity of the system represented by the graph. We explore minimal and maximal values of the defined measures and comment on the topology of graphs for which maximal and minimal values are obtained. Potentially, the proved bounds could be used to benchmark existing algorithms, devise new approximation algorithms or branch and bound schemas for some scheduling problems that are usually of hard computational complexity.</p>https://www.ejgta.org/index.php/ejgta/article/view/1212directed acyclic graph, topological order, measure, extremal values |
| spellingShingle | Suzana Antunović Damir Vukičević Evaluating topological ordering in directed acyclic graphs Electronic Journal of Graph Theory and Applications directed acyclic graph, topological order, measure, extremal values |
| title | Evaluating topological ordering in directed acyclic graphs |
| title_full | Evaluating topological ordering in directed acyclic graphs |
| title_fullStr | Evaluating topological ordering in directed acyclic graphs |
| title_full_unstemmed | Evaluating topological ordering in directed acyclic graphs |
| title_short | Evaluating topological ordering in directed acyclic graphs |
| title_sort | evaluating topological ordering in directed acyclic graphs |
| topic | directed acyclic graph, topological order, measure, extremal values |
| url | https://www.ejgta.org/index.php/ejgta/article/view/1212 |
| work_keys_str_mv | AT suzanaantunovic evaluatingtopologicalorderingindirectedacyclicgraphs AT damirvukicevic evaluatingtopologicalorderingindirectedacyclicgraphs |