Bounded degree acyclic decompositions of digraphs |
| |
Authors: | David R Wood |
| |
Institution: | 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 s 2 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 等数据库收录! |