Przeszukiwanie struktur grafowych - Project - Bridge of Knowledge

Search

Przeszukiwanie struktur grafowych

Problematyka przeszukiwania struktur grafowych zyskuje obecnie na znaczeniu, a jednocześnie stanowi już dojrzałą i silnie ugruntowaną dziedzinę badań. Wśród głównych powodów tego faktu można wymienić potencjalne zastosowania oraz silne związki z klasyczną teorią grafów. Dotychczas opisano bardzo wiele modeli przeszukiwania grafów, które zazwyczaj znajdują swoje motywacje w jednym z dwóch powyższych źródeł. W ogólności problem przeszukiwania grafu definiowany jest jako gra pomiędzy dwiema stronami. Jedna ze stron (\emph{poszukujący}) jest odpowiedzialna za odnalezienie celu znajdującego się w odpowiedniej strukturze (grafowej lub geometrycznej), natomiast celem drugiej strony jest pozostanie ukrytym lub nieschwytanym tak długo jak to możliwe. Różnorodne modele znajdują swoje źródła w potencjalnych charakterystykach obu stron, a także w cechach struktury, w której odbywa się powyższa gra. Do typowych charakterystyk obu stron można zaliczyć mobilność, wiedzę czy widoczność. Cechy struktury dyktują podział na problemy grafowe lub geometryczne, prowadząc do kolejnych podziałów w każdej z kategorii. Związki problemów i modeli przeszukiwania grafów z klasyczną teorią grafów stoją niejako u podstaw tego nurtu badań --- odkrycia pozwalające na uzyskanie równoważnych definicji takich parametrów grafowych jak pathwidth, treewidth czy bandwidth, właśnie za pomocą gier przeszukiwawczych, spowodowały gwałtowny rozwój tej nowych modeli przeszukiwania grafów. W konsekwencji odkryto wiele powiązań powyższego typu. Potencjał ku dalszym odkryciom w tym kierunku jest nadal olbrzymi, co stanowi silną motywacją ku podejmowaniu tej tematyki badań. W tym upatrujemy jedną z motywacji ku podjęciu tego tematu --- wyniki uzyskane dla problemów przeszukiwania grafów mogą mieć szerszy wpływ na inne działy teorii grafów. Potencjalne zastosowania podejmowanej problematyki obejmują zagadnienia modelowania ruchu mobilnych autonomicznych jednostek w celu przeszukiwania terenu. Pewne nurty badań w tym kierunku dotyczą kwestii modelowania terenu. W tym zakresie podstawowym akceptowanym modelem jest graf, jako dyskretyzacja ciągłej przestrzeni przeszukiwania, ale także znaczący nurt obecnych badań dotyczy matematycznej analizy struktur geometrycznych. Grafowe i geometryczne modele są niejednokrotnie komplementarne, stąd w niniejszym wniosku planujemy badania w obydwu kierunkach.

Details

Financial Program Name:
OPUS
Organization:
Narodowe Centrum Nauki (NCN) (National Science Centre)
Agreement:
UMO-2015/17/B/ST6/01887 z dnia 2016-01-27
Realisation period:
2016-01-27 - 2019-01-26
Project manager:
prof. dr hab. inż. Dariusz Dereniowski
Realised in:
Faculty of Electronics, Telecommunications and Informatics
Project's value:
287 280.00 PLN
Request type:
National Research Programmes
Domestic:
Domestic project
Verified by:
Gdańsk University of Technology

seen 227 times