Wykład prof. Leonidasa Paliosa na WMiI UŁ

Oddział Łódzki PTM serdecznie zaprasza na wykład prof. Leonidasa Paliosa z University of Ioannina, Department of Computer Science and Engineering, pod tytułem “Recognizing HH-free and HHD-free graphs”, który odbędzie się w dniu 21 maja 2019 roku (wtorek) o godz. 12.15 w sali D103 WMiI UŁ.



In this talk, we consider the recognition problem for the classes of HH-free and HHD-free graphs. A graph is HH-free if it contains no induced subgraph isomorphic to a “house” or a “hole”, whereas an HHD-free graph is an HH-free graph that contains no induced “domino”.

First, we will exhibit properties of the chordal completion of a graph and will describe a modified version of the well known linear-time algorithm to test for a perfect elimination ordering which we use to recognize if a graph on n vertices and m edges is HH-free in O(min{n m a(n),n m+n^2  log n}) time and O(n+m) space. This algorithm implies an HHD-free recognition algorithm with the same time and space complexity.

Next, we will present an improved algorithm for recognizing HHD-free graphs which takes O(nm) time and O(n+m) space. Both algorithms can be augmented to provide a certificate (an induced house, hole, or domino) whenever they decide that the input graph is not HH-free or HHD-free.

The certificate computation requires O(n+m) additional time and O(n) space.

This is joint work with Stavros D. Nikolopoulos, University of Ioannina, Greece.

Z upoważnienia,

Prof. nadzw. dr. hab. Marka Majewskiego

Pełnomocnik Dziekana ds. promocji WMiI UŁ


Copyright © 2020 Wydział Matematyki i Informatyki UŁ. All rights reserved.