Interaction over time and fixed-parameter tractable algorithm on (Bi-)sparse split problem of graph.
: 10h00, ngày 15/06/2020 (Thứ Hai)
: P106 D3, ĐH BKHN
: Seminar Toán rời rạc
: Phan Thi Ha Duong
: Viên Toán học, Viện Hàn lâm Khoa học và Công nghệ Việt Nam
Tóm tắt báo cáo
Interactions over time, such as phone calls, computer communications, physical proximity between individuals, shopping have been studied for a long time and have been captured in the link stream framework. Intuitively, a link stream is a sequence of pairs of the form (I; uv) where uv is an edge and I a time interval.
A link stream is (bi-)sparse split if it consists of a (two) clique(s) on an (two) interval times. Problem sparse split (resp. bi-sparse split) link stream edition asks to transform an arbitrary link stream into a sparse split (resp. bi-sparse split) link stream by performing at most some given number of modications on its timed edges.
We give a generic approach to devise fixed parameter tractable algorithms for link stream edition problems and exemplify two particular problems: sparse split and bi-sparse split edition.