| [home] - [up] |
Abstract: Root finding is a fundamental concept in many areas of mathematics. A graph H is a square root of graph G if G is isomorphic to the square of H. The general square root problem in graph theory often places restrictions on the family to which graph H belongs and studies the complexity of determining whether given graph G has a square root in family X. For example, polynomial time algorithms are known for X being trees or cographs, whereas the general problem, where X is arbitrary graphs is NP-complete. In this talk we sketch polynomial time algorithms for X being bipartite or proper interval graphs. Furthermore, new NP-completeness results are presented that indicate that these polynomial time algorithms can not be significantly generalized unless P=NP. (Joint work with Lap Chi Lau.)
Colloquium - 16:00
Abstract: