FORMI 4-SEG
Forbidden Minor Characterizations For 4-Searchable Graphs
| Coordinatore | KADIR HAS UNIVERSITESI
Organization address
address: HISARALTI CAD CIBALI FATIH CIBALI MERKEZ CAMPUS contact info |
| 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
| # | ||||
|---|---|---|---|---|
| 1 |
KADIR HAS UNIVERSITESI
Organization address
address: HISARALTI CAD CIBALI FATIH CIBALI MERKEZ CAMPUS contact info |
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.