Joyce Bacic

dblp:305/0358 · DBLP profile ↗
← Back
2ranked-venue papers
2as first author
2since 2021 · last 2023
0000-0002-6202-816XORCID · reported

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 first-author · 2 since 2021
YearPublicationVenuePosition
2023 Shortest Beer Path Queries in Outerplanar Graphs
abstract
A beer graph is an undirected graph G, in which each edge has a positive weight and some vertices have a beer store. A beer path between two vertices u and v in G is any path in G between u and v that visits at least one beer store. We show that any outerplanar beer graph G with n vertices can be preprocessed in O(n) time into a data structure of size O(n), such that for any two query vertices u and v, (i) the weight of the shortest beer path between u and v can be reported in $$O(\alpha (n))$$ time (where $$\alpha (n)$$ is the inverse Ackermann function), and (ii) the shortest beer path between u and v can be reported in O(L) time, where L is the number of vertices on this path. Note that the running time for (ii) does not depend on the number of vertices of G. Both results are optimal, even when G is a beer tree (i.e., a beer graph whose underlying graph is a tree).
Joyce Bacic, Saeed Mehrabi 0001, Michiel H. M. Smid
Algorithmica1
2021 Shortest Beer Path Queries in Outerplanar Graphs
Joyce Bacic, Saeed Mehrabi 0001, Michiel H. M. Smid
ISAAC1