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 be a fixed collection of digraphs. Given a digraph H, a -packing of H is a collection of vertex disjoint subgraphs of H, each isomorphic to a member of . For undirected graphs, Loebl and Poljak have completely characterized the complexity of deciding the existence of a perfect -packing, in the case that consists of two graphs one of which is a single edge on two vertices. We characterize -packing where consists of two digraphs one of which is a single arc on two vertices. |
| |
Keywords: | Computational complexity Graph algorithms Graph packings |
本文献已被 ScienceDirect 等数据库收录! |
|