FORMI 4-SEG

Forbidden Minor Characterizations For 4-Searchable Graphs

Coordinatore	KADIR HAS UNIVERSITESI    more  Organization address address: HISARALTI CAD CIBALI FATIH CIBALI MERKEZ CAMPUS city: ISTANBUL postcode: 34230 contact info Titolo: Prof. Nome: Mustafa Cognome: Aydin Email: send email Telefono: +90 212 5336532 Fax: +90 212 5336515
Nazionalità Coordinatore	Turkey [TR]
Totale costo	75˙000 €
EC contributo	75˙000 €
Programma	FP7-PEOPLE Specific programme "People" implementing the Seventh Framework Programme of the European Community for research, technological development and demonstration activities (2007 to 2013)
Code Call	FP7-PEOPLE-2010-RG
Funding Scheme	MC-IRG
Anno di inizio	2011
Periodo (anno-mese-giorno)	2011-09-01   -   2014-08-31

 Partecipanti

#	participant	country	role	EC contrib. [€]
1	KADIR HAS UNIVERSITESI  Organization address address: HISARALTI CAD CIBALI FATIH CIBALI MERKEZ CAMPUS city: ISTANBUL postcode: 34230 contact info Titolo: Prof. Nome: Mustafa Cognome: Aydin Email: send email Telefono: +90 212 5336532 Fax: +90 212 5336515	TR (ISTANBUL)	coordinator	75˙000.00

Mappa

 Word cloud

Esplora la "nuvola delle parole (Word Cloud) per avere un'idea di massima del progetto.

 Obiettivo del progetto (Objective)

'Edge searching is a pursuit evasion game played on graphs. In the past two decades there has been fundamental work devoted to this topic by scientists in many diverse fields due to its highly interdisciplinary nature. We consider the problem of constructing a search plan in order to find a person lost in a system of caves which can be represented as a graph G. Equivalently, we aim to clean a network of tunnels filled with noxious gas using as few cleaners as possible. This minimum number for a graph G is the edge search number of G, and it is denoted as s(G). The problem has wide range of applications from network security to VLSI chip design. One of the major problems of edge searching is to characterize the graphs G such that s(G) is at most k, for a fixed positive integer k. This problem is solved only for k=1, 2 and 3 (Megiddo et. al. 1976). The problem has been considered as an open problem that has high priority. In this project our objective is to characterize those graphs for which k=4 searchers suffice and to generalize this characterization to any k>4. Our main contribution will be deriving a constructive characterization which works more efficient than the previous results. During the project we aim to improve the existing European interest on the subject and to start new discussions.'

Introduzione (Teaser)

EU-funded scientists are seeking to determine the minimum searchers' number (k number) required to catch an intruder in a system of caves.