dc.contributor.author | Dvořák, Zdeněk | |
dc.date.accessioned | 2024-03-04T09:10:51Z | |
dc.date.available | 2024-03-04T09:10:51Z | |
dc.date.issued | 2023 | |
dc.identifier.uri | https://hdl.handle.net/20.500.14178/2303 | |
dc.description.abstract | A partial orientation H⃗ of a graph G is a weak r-guidance system if for any two vertices at distance at most r in G, there exists a shortest path P between them such that H⃗ directs all but one edge in P towards this edge. In case that H⃗ has bounded maximum outdegree Delta , this gives an efficient representation of shortest paths of length at most r in G: For any pair of vertices, we can either determine the distance between them or decide the distance is more than r, and in the former case, find a shortest path between them, in time O(Delta^r). We show that graphs from many natural graph classes admit such weak guidance systems, and study the algorithmic aspects of this notion. We also apply the notion to obtain approximation algorithms for distance variants of the independence and domination number in graph classes that admit weak guidance systems of bounded maximum outdegree. | en |
dc.language.iso | en | |
dc.publisher | Schloss-Dagstuhl - Leibniz Zentrum für Informatik | |
dc.relation.url | https://doi.org/10.4230/LIPIcs.STACS.2023.28 | |
dc.rights | Creative Commons Uveďte původ 4.0 International | cs |
dc.rights | Creative Commons Attribution 4.0 International | en |
dc.title | Representation of Short Distances in Structurally Sparse Graphs | en |
dcterms.accessRights | openAccess | |
dcterms.license | https://creativecommons.org/licenses/by/4.0/legalcode | |
dc.date.updated | 2024-03-04T09:10:51Z | |
dc.subject.keyword | distances | en |
dc.subject.keyword | structurally sparse graphs | en |
dc.publisher.publicationPlace | Wadern, Germany | |
dc.relation.fundingReference | info:eu-repo/grantAgreement/MSM/LL/LL2005 | |
dc.relation.fundingReference | info:eu-repo/grantAgreement/EU/FP8/DYNASNET | |
dc.relation.fundingReference | info:eu-repo/grantAgreement/UK/COOP/COOP | |
dc.date.embargoStartDate | 2024-03-04 | |
dc.type.obd | 57 | |
dc.type.version | info:eu-repo/semantics/publishedVersion | |
dc.identifier.doi | 10.4230/LIPIcs.STACS.2023.28 | |
dc.identifier.eidScopus | 2-s2.0-85149854759 | |
dc.identifier.obd | 641472 | |
dc.subject.rivPrimary | 10000::10200::10201 | |
dcterms.isPartOf.name | Leibniz International Proceedings in Informatics, LIPIcs | |
dcterms.isPartOf.journalYear | 2023 | |
dcterms.isPartOf.journalVolume | 254 | |
dcterms.isPartOf.isbn | 978-3-95977-266-2 | |
uk.faculty.primaryId | 116 | |
uk.faculty.primaryName | Matematicko-fyzikální fakulta | cs |
uk.faculty.primaryName | Faculty of Mathematics and Physics | en |
uk.department.primaryId | 2110 | |
uk.department.primaryName | Informatický ústav UK | cs |
uk.department.primaryName | Informatický ústav UK | en |
uk.event.name | International Symposium on Theoretical Aspects of Computer Science | |
dc.description.pageRange | 1-22 | |
dc.type.obdHierarchyCs | PŘÍSPĚVEK V KONFERENČNÍM SBORNÍKU::příspěvek v konferenčním sborníku::příspěvek v recenzovaném konferenčním sborníku | cs |
dc.type.obdHierarchyEn | PAPER IN CONFERENCE PROCEEDINGS::article in proceedings::article in reviewed proceedings | en |
dc.type.obdHierarchyCode | 57::148::499 | en |
uk.displayTitle | Representation of Short Distances in Structurally Sparse Graphs | en |