Strong Arc Decomposition Problem
摘要
Recall that it is NP-complete to decide whether a digraph has a strong arc decomposition (Theorem 1.2 ), therefore it is natural to consider this problem on some digraph classes. In this chapter, we introduce most of known results on semicomplete digraphs, locally semicomplete digraphs, digraph compositions and digraph products. We also introduce Kelly conjecture and Bang-Jensen–Yeo conjecture which are highly related to the strong arc decomposition problem.