Academic Journal
Non-crossing shortest paths lengths in planar graphs in linear time
| العنوان: | Non-crossing shortest paths lengths in planar graphs in linear time |
|---|---|
| المؤلفون: | Balzotti, Lorenzo, Franciosa, Paolo G. |
| المساهمون: | Balzotti, Lorenzo, Franciosa, Paolo G. |
| بيانات النشر: | Elsevier |
| سنة النشر: | 2024 |
| المجموعة: | Sapienza Università di Roma: CINECA IRIS |
| مصطلحات موضوعية: | shortest path, undirected planar graph, non-crossing paths |
| الوصف: | Given a plane graph it is known how to compute the union of non-crossing shortest paths. These algorithms do not allow neither to list each single shortest path nor to compute length of shortest paths. Given the union of non-crossing shortest paths, we introduce the concept of shortcuts that allows us to establish whether a path is a shortest path by checking local properties on faces of the graph. By using shortcuts we can compute the length of each shortest path, given their union, in total linear time, and we can list each shortest path p in O(max{l,l log log kl}), where l is the number of edges in p and k the number of shortest paths. |
| نوع الوثيقة: | article in journal/newspaper |
| اللغة: | English |
| Relation: | info:eu-repo/semantics/altIdentifier/wos/WOS:001145058700001; volume:346; issue:March 2024; firstpage:183; lastpage:191; numberofpages:9; journal:DISCRETE APPLIED MATHEMATICS; https://hdl.handle.net/11573/1703578; info:eu-repo/semantics/altIdentifier/scopus/2-s2.0-85180968575 |
| DOI: | 10.1016/j.dam.2023.12.011 |
| الاتاحة: | https://hdl.handle.net/11573/1703578 https://doi.org/10.1016/j.dam.2023.12.011 |
| Rights: | info:eu-repo/semantics/openAccess |
| رقم الانضمام: | edsbas.8A6D8068 |
| قاعدة البيانات: | BASE |
| DOI: | 10.1016/j.dam.2023.12.011 |
|---|