Shortest beer path queries in outerplanar graphs

Abstract: A emph{beer graph} is an undirected graph

G

, in which each edge has a positive weight and some vertices have a beer store. A emph{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 (a l p h a (n))

time (where

a l p h a (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. Both results are optimal, even when

G

is a beer tree (i.e., a beer graph whose underlying graph is a tree).

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Shortest beer path queries in outerplanar graphs