首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 sgreater-or-equal, slanted2 every digraph has an acyclic decomposition into s subgraphs such that in each subgraph the outdegree of each vertex v is at most Image . For all digraphs this degree bound is optimal.
Keywords:Author Keywords: Digraph  Acyclic subgraph  Acyclic decomposition  Arboricity  Diarboricity
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号