Chain packing in graphs

Shigeru Masuyama, Toshihide Ibaraki

Research output: Contribution to journalArticle

10 Citations (Scopus)

Abstract

This paper discusses the complexity of packing k-chains (simple paths of length k) into an undirected graph; the chains packed must be either vertex-disjoint or edge-disjoint. Linear-time algorithms are given for both problems when the graph is a tree, and for the edge-disjoint packing problem when the graph is general and k = 2. The vertex-disjoint packing problem for general graphs is shown to be NP-complete even when the graph has maximum degree three and k = 2. Similarly the edge-disjoint packing problem is NP-complete even when the graph has maximum degree four and k = 3.

Original languageEnglish
Pages (from-to)826-839
Number of pages14
JournalAlgorithmica
Volume6
Issue number1
DOIs
Publication statusPublished - 1 Dec 1991

    Fingerprint

Keywords

  • Chain packing
  • Computational complexity
  • Graph algorithms
  • Graph packing
  • Linear-time algorithms
  • NP-completeness

Cite this