Univerza na Primorskem Fakulteta za matematiko, naravoslovje in informacijske tehnologije
-->
SI | EN

petek, 22. november 2019 Nevena PIVAČ: On the Graph Search Trees

V ponedeljek, 25. novembra 2019, bo ob 16.00 uri v prostorih Fakultete za matematiko, naravoslovje in informacijske tehnologije Univerze na Primorskem, Glagoljaška 8, Koper
predavanje v okviru PONEDELJKOVEGA SEMINARJA RAČUNALNIŠTVA IN INFORMATIKE
Oddelkov za Informacijske znanosti in tehnologije UP FAMNIT in UP IAM.

ČAS in PROSTOR:  25. november 2019 ob 16.00 v FAMNIT-VP2

---------------------------------------------
PREDAVATELJICA: Nevena PIVAČ
---------------------------------------------

Nevena Pivač is a student of two study programs: MSc in Computer Science and PhD in Mathematics, at UP FAMNIT. She is doing PhD under the supervision of full professor Martin Milanič and is employed as a young researcher at Institute Andrej Marušič. Her research topics include structural and algorithmic graph theory, combinatorial optimization, and mathematical modeling using integer linear programing.

--------------------------------------------------
NASLOV: On the Graph Search Trees
--------------------------------------------------

POVZETEK:

Graph searches and the corresponding search trees can exhibit important structural properties and are used in various graph algorithms. We present various graph search algorithms, such as breadth first search (BFS), depth first search (DFS), their lexicographic versions (LBFS, LDFS), maximal neighborhood search (MNS) and maximum cardinality search (MCS). The problem of deciding whether a given spanning tree of a graph is a search tree of a particular search on this graph was introduced by Hagerup and Nowak in 1985, and independently by Korach and Ostfeld in 1989 where the authors showed that this problem is efficiently solvable for DFS trees. We show that the search tree problem is polynomial-time solvable for LDFS, in contrast to LBFS, MCS, and MNS, where we show the NP-completeness.
Joint work with Jesse Beisegel, Carolin Denkert, Ekkehard Kohler, Matjaž Krnc, Robert Scheffler, and Martin Strehler.

Predavanje bo potekalo v angleškem jeziku.