TY - JOUR
AU - Frank Gurski
PY - 2017/03/04
Y2 - 2023/02/09
TI - Dynamic Programming Algorithms on Directed Cographs
JF - Statistics, Optimization & Information Computing
JA - Stat., optim. inf. comput.
VL - 5
IS - 1
SE - Research Articles
DO - 10.19139/soic.v5i1.260
UR - http://www.iapress.org/index.php/soic/article/view/20170303
AB - In this paper we consider directed cographs, which are defined by Bechet et al. by the disjoint union, series, and order composition, from an algorithmic point of view. Using their recursive structure we give dynamic programming algorithms to show that for every directed cograph the size of a largest edgeless subdigraph, the size of a largest subdigraph which is a tournament, the size of a largest semicomplete subdigraph, and the size of a largest complete subdigraph can be computed in linear time. Our main results show that the hamiltonian path, hamiltonian cycle, regular subdigraph, and directed cut problem are polynomial on directed cographs.
ER -