Bounded degree acyclic decompositions of digraphs |
| |
Authors: | David R. Wood |
| |
Affiliation: | School of Computer Science, Carleton University, 1125 Colonel By Drive, Ottawa, Ont., Canada K1S 5B6 |
| |
Abstract: | An acyclic decomposition of a digraph is a partition of the edges into acyclic subgraphs. Trivially every digraph has an acyclic decomposition into two subgraphs. It is proved that for every integer s2 every digraph has an acyclic decomposition into s subgraphs such that in each subgraph the outdegree of each vertex v is at most . For all digraphs this degree bound is optimal. |
| |
Keywords: | Author Keywords: Digraph Acyclic subgraph Acyclic decomposition Arboricity Diarboricity |
本文献已被 ScienceDirect 等数据库收录! |