Font size: Αα Αα Αα hide gadgets
You are here: Seminars » 2012-2013 » R. Belmonte, 2012-11-30 { prev, contents, next }
download seminar details: { pdf }


Photo of Belmonte
Speaker: Rémy Belmonte (Υποψήφιος διδάκτορας, University of Bergen)
Title: Induced immersions
Date: Παρασκευή, 30 Νοέ 2012
Ώρα: 18:30-19:30
Location: Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών, Τμήμα Μαθηματικών, room Γ33


A graph G contains a multigraph H as an induced immersion if H can be obtained from G by a sequence of vertex deletions and lifts. We present a polynomial-time algorithm that decides for any fixed multigraph H whether an input graph G contains H as an induced immersion. We also show that for every multigraph H with maximum degree at most 2, there exists a constant c_H such that every graph with treewidth more than c_H contains H as an induced immersion.


You must be logged in to comment.


Web standards: XHTML1.0, CSS3.
© 1996 – 2018 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.