26.märts, 14:00 ICT-315 "Linear-time algorithms for two graph problems (coloring and 2-dominating) on a class of perfect graphs"
Tarkvarateaduse instituudi seminaril esmaspäeval, 26.03.2018 kell 14:00 esineb Stavros D. Nikolopoulos (Joonia Ülikool, Kreeka) teemal "Linear-time algorithms for two graph problems (coloring and 2-dominating) on a class of perfect graphs".
Seminar toimub ruumis ICT-315.
In a graph theoretic framework, a coloring is a partition V(G)=V1 + V2 + … + Vc of the vertex set of a graph G such that each partition set is a stable set; the coloring problem asks for a minimum such c. The 2-domination problem on a graph G asks for a minimum-cardinality dominating set S of G such that the subgraph induced by S contains a perfect matching; motivation for this problem comes from the interest in finding a small number of locations to place pairs of mutually visible guards so that the entire set of guards monitors a given area. Both, the coloring and the 2-domination problems on general graphs are known to be NP-complete.
This talk will focus on some of our latest results showing that both problems have polynomial-time solutions on a well known class of perfect graphs, namely, permutation graphs. We define an embedding of permutation graphs in the plane which enables us to obtain equivalent versions of the problems involving longest paths in directed graphs and domination relations of points in the plane. The presented algorithms compute a coloring and a 2-dominating set of a permutation graph G on n vertices and m edges in O(n+m) time and, thus, they provide optimal solutions to both problems; it is worth noting that our algorithms run also optimally in O(n) time if we are given the permutation defining the graph G.