Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, February 23, 2006, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Masashi Kiyomi (National Institute of Informatics (NII)
In this talk, we address the problem of enumerating all chordal subgraphs in a given graph. Graph is chordal iff it has no induced chordless cycle of length more than three. We introduce an algorithm to enumerate all chordal subgraphs in an n-vertices complete graph. Then, we show that we can use, with small changes, these algorithms to generate all (connected or not necessarily connected) chordal subgraphs in arbitrary graph. Our algorithms are based on reverse search method, and time complexities to generate a chordal graph are O(1).
Automatic MiSe System Software Version 1.4803M | admin login