This is a static snapshot of the website of MPLA, taken on 2025-02-27.
You are here: Seminars » 2012-2013 » R. Belmonte, 2012-11-30

Seminar

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

Abstract

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.

Comments

Reporter

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