In this Seminar, (Bachelor and Master) students will present extracts from recent articles on graph convexities, which investigate propagation effects in graph networks, as well as other related structural dissemination problems. The idea is to investigate the complexitiy (linear, polynomial, or NP-Hard, for instance) of these problems. For example, if a company wants to spread a rumour on a new product, it might want to select few key influential individuals to initiate a viral marketing on some popular social internet or smartphone framework which would spread very fast positive remarks to a crowd of potential consumers, How the graph network of relationships gets covered by the Information dissemination depends on the rule for new people to join in.
The seminar will start on the second week of class and up to 12 students are allowed.
If interested to register, please send an email to Dr. Penso.
Any topic within this context is welcome. To give an idea and some taste of the themes, some article examples with polynomial algorithms and NP-Hard results follow:
M. C. Dourado, Lucia Draque Penso, D. Rautenbach:
Geodetic Convexity Parameters for Graphs with Few Short Induced Paths. WG 2016: 25-37
C. C. Centeno, Lucia Draque Penso, D. Rautenbach, V.G.P. de Sa:
Immediate versus Eventual Conversion: Comparing Geodetic and Hull Numbers in P 3-Convexity. WG 2012: 262-273