CS Seminar: "Recognizing HH-free and HHD-free graphs"

15 March 2017

Professor Leonidas Palios, Computer Science and Engineering Department, University of Ioannina, Greece will deliver a research talk in the area of Algorithms (Graphs), as part of an Erasmus visit with the Department of Computer Science. 

 
Title of the talk: "Recognizing HH-free and HHD-free graphs"
 
Date and Venue: Wednesday, March 15, 2017, 15:00 in B209
 

Abstract:

A house graph is a cycle on 5 vertices with a single chord. A hole is a chordless graph on at least 5 vertices. A domino is a cycle on 6 vertices with a single long chord. A graph is HH-free if it contains no house or hole, whereas it is HHD-free if it contains no house, hole, or domino. The classes of both HH-free and HHD-free graphs are subclasses of the well known class of perfect graphs. In this talk, we present algorithms for recognizing whether a given graph is HH-free or HHD-free, namely, the algorithms of Hoang and Sritharan, and of Nikolopoulos and Palios.
 

Speaker's Short Bio:

Leonidas Palios received his Diploma of Electrical and Computer Engineering from the National Technical University of Athens in 1987, and his PhD from Princeton University in 1992. Until the end of 1995, he was at the University of Minnesota where he pursued postgraduate studies at the Geometry Center and was adjunct professor for two semesters at the Computer Science Department. Since 1997, he has been at the Computer Science and Engineering Department of the University of Ioannina, where he now is a professor. His research interests include Design and Analysis of Algorithms with emphasis on Algorithmic Graph Theory and Computational Geometry.