mpla.math.uoa.gr
Font size: Αα Αα Αα hide gadgets
You are here: Seminars » 2014-2015 » P. A. Golovach, 2014-10-17 { prev, contents, next } Anonymously browsing from 54.158.214.111 at 21:33:50, 17-11-2017. login
download seminar details: { pdf }

Seminar

Photo of Golovach
Speaker: Petr A. Golovach (Петр А. Головач)
Title: Hadwiger number of graphs with small chordality
Date: Friday, 17 Oct 2014
Time: 18:30-19:20
Location: Univeristy of Athens, Department of Mathematics, University of Athens, room Γ33

Abstract

The Hadwiger number of a graph G is the largest integer h such that G has the complete graph K_h as a minor. We show that the problem of determining the Hadwiger number of a graph is NP-hard on co-bipartite graphs, but can be solved in polynomial time on cographs and on bipartite permutation graphs. We also consider a natural generalization of this problem that asks for the largest integer h such that G has a minor with h vertices and diameter at most s. We show that this problem can be solved in polynomial time on AT-free graphs when s>1, but is NP-hard on chordal graphs for every fixed s>1.

Comments

You must be logged in to comment.

Reporter

Page updates

No recent updates.

Feeds RSS and Atom feeds

posts
all posts RSS
news RSS
announcements RSS
website news RSS
events
all events RSS
defenses RSS
exams RSS
seminars RSS
graduations RSS
Web standards: XHTML1.0, CSS3.
© 1996 – 2017 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.