[Turkmath:6618] Bogazici Matematik Carsamba Seminerleri - ilan ekte

[ferit.ozturk at boun.edu.tr]

Konuşmalar İngilizce yapılmaktadır.

--------------------------------------------------

BOGAZICI UNIVERSITY MATH COLLOQUIUM

Edge Searching

Oznur Yasar
Memorial University of Newfoundland, Canada

Date : Wednesday, October 21, 2009
Time : 14:00
Place : TB 250, Boğaziçi Üniversitesi

Abstract:
Edge searching is a combinatorial game played on graphs. It corresponds to
capturing an intruder in a graph with a minimum
number of searchers. This minimum is called the search number of the graph. It
is a graph invariant that is related to other graph parameters such chromatic
number and pathwidth.  In the original game it is assumed that each edge of the
graph is cleaned in the same way and initially each edge has equal
contamination
that can be considered a weight of one. We modify the problem and consider it
on
graphs with arbitrary positive integer weights assigned to their edges. We
first
show that for every weighted graph the minimum number of searchers needed for a
not-necessarily-monotonic weighted search is enough for a monotonic weighted
search, where each edge is cleaned only once and prove the NP-completeness of
the problem. We then consider fast searching, that is, a monotone search where
no edge is traversed more than once and the searchers are not allowed to jump.
We present a linear time algorithm to compute the fast search number of trees.
We close with a note on the search number of circulant graphs on cyclic groups
of prime order.


Tea and coffee will be served at 15:00
-------------- sonraki bölüm --------------
Yazı olmayan bir eklenti temizlendi...
Ä°sim: 102109OznurYasar.pdf
Tür: application/pdf
Boyut: 84488 bayt
Tanım: kullanılamıyor
Url: http://yunus.listweb.bilkent.edu.tr/pipermail/turkmath/attachments/20091016/3fded891/attachment-0001.pdf