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

Seminar

Photo of Belmonte
Speaker: Rémy Belmonte (PhD student, University of Bergen)
Title: Induced immersions
Date: Friday, 30 Nov 2012
Time: 18:30-19:30
Location: Univeristy of Athens, Department of Mathematics, University of Athens, 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

You must be logged in to comment.

Reporter

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