Bakalářská práce

Beer Shortest Path Problem in Dynamic Graphs

Štěpán Lukeš
Anotace

Problém pivních cest (beer path problem) je varianta problému nejkratších cest, ve které nalezená cesta musí procházet alespoň jedním určeným bodem zájmu. Existující předzpracovací techniky, jako je Weighted Highway Labeling, umožňují efektivní zodpovídání dotazů ve statických grafech, jejich údržba se však stává obtížnou, pokud se struktura grafu dynamicky mění. Tato práce se zabývá problémem pivních …více

Abstract

The beer path problem is a shortest-path variant in which the computed path must traverse at least one designated point of interest. Existing preprocessing techniques, such as Weighted Highway Labeling, allow efficient query answering in static graphs, but become difficult to maintain when the graph structure changes dynamically. This thesis studies the beer path problem in dynamic weighted graphs …více

Klíčová slova
shortest path problem beer path problem dynamic graphs graph algorithms distance labeling highway labeling weighted highway labeling
Zadání práce
The beer path problem captures the option of visiting points of interest, such as gas stations or convenience stops, prior to reaching the final destination. The problem was intensively studied for temporal graphs in [1]. The goal of the bachelor's thesis is to introduce the concept of beer paths in dynamic graphs, where points of interest can change dynamically. The thesis proposes efficient algorithms for the problem together with a preprocessing techniques that enable efficient query answering under dynamic conditions.
Administrativní informace
Práce zkontrolována:
24. 5. 2026 17:04, prof. RNDr. Ivana Černá, CSc., učo 1419
Plný text práce
531 KB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
25. 6. 2026
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Ivana Černá, CSc., učo 1419
KTP FI MU

Oponent

RNDr. Jaromír Plhák, Ph.D., učo 60773
KSUZD FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Plán
Informatika

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.