Recognizing digraphs of Kelly-width 2 |
| |
Authors: | Daniel Meister Jan Arne Telle |
| |
Institution: | Department of Informatics, University of Bergen, Norway |
| |
Abstract: | Kelly-width is a parameter of digraphs recently proposed by Hunter and Kreutzer as a directed analogue of treewidth. We give an alternative characterization of digraphs of bounded Kelly-width in support of this analogy, and the first polynomial-time algorithm recognizing digraphs of Kelly-width 2. For an input digraph G=(V,A) the algorithm outputs a vertex ordering and a digraph H=(V,B) with A⊆B witnessing either that G has Kelly-width at most 2 or that G has Kelly-width at least 3, in time linear in H. |
| |
Keywords: | Digraph width parameter Kelly-width Characterization Recognition |
本文献已被 ScienceDirect 等数据库收录! |