Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 16.11.2006 at 12:20 in S5, there is the following noon lecture:

On Recognition of PC-graphs

Martin Pergel

Abstract

Polygon-circle graphs (shortly PC-graphs), defined as intersection graphs of polygons inscribed into a circle, form an intersection class generalizing many other classes (i. e., interval, circle, circular-arc, chordal graphs and cactus-subtree graphs). We introduce a polynomial-time algorithm for recognition of PC-graphs with girth at least 5 and show that the general PC-graph recognition is an NP-complete problem.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010