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


On the complexity of digraph packings
Authors:Richard C. Brewster  Romeo Rizzi
Affiliation:a Computer Science Department, Bishop's University, Lennoxville, Quebec, Canada, J1M 1Z7
b Dipartimento di Informatica e Telecomunicazioni, Università di Trento, via Sommarvie 14, 38050 Povo, Italy
Abstract:Let View the MathML source be a fixed collection of digraphs. Given a digraph H, a View the MathML source-packing of H is a collection of vertex disjoint subgraphs of H, each isomorphic to a member of View the MathML source. For undirected graphs, Loebl and Poljak have completely characterized the complexity of deciding the existence of a perfect View the MathML source-packing, in the case that View the MathML source consists of two graphs one of which is a single edge on two vertices. We characterize View the MathML source-packing where View the MathML source consists of two digraphs one of which is a single arc on two vertices.
Keywords:Computational complexity   Graph algorithms   Graph packings
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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