One-Sided Weak Dominance Drawing: Complexity and Algorithms

Speaker: Prof. Sebastián Urrutia

Title: One-Sided Weak Dominance Drawing: Complexity and Algorithms

Abstract:  

The Weak Dominance Drawing problem can be defined as follows: given a directed acyclic graph G, find two topological sorts, t_X and t_Y, minimizing the size of the intersection between them. The intersection of two topological sorts is defined as the set of ordered pair of vertices (u, v) such that t_X(u) < t_X(v) and t_Y(u) < t_Y(v). In this work we consider a variation of this problem, that we call One-Sided Weak Dominance Drawing, in which one of the topological sorts is given as input and we must find another topological sort minimizing the intersection set with the given one. This problem has been considered in the literature and its applications include index generation of competitive algorithms for reachability queries on very large graphs. In this work we formalize the problem, describe one of its applications, prove that its decision version is NP-complete and determine a primal bound for it as a function of the dimension of G.

For registration, please send an email to Ahmad Hemmati.