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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Strong Arc Decomposition Problem

  • Yuefang Sun

摘要

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.