Chain packing in graphs

DOI10.1007/BF01759074zbMATH Open0731.68088OpenAlexW2006069852MaRDI QIDQ808291FDOQ808291

Authors: Shigeru Masuyama, Toshihide Ibaraki 

Publication date: 1991

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01759074

Recommendations

• Packingk-edge trees in graphs of restricted vertex degrees
• scientific article; zbMATH DE number 1960287
• On the tractability of some natural packing, covering and partitioning problems
• The path set packing problem
• Edge disjoint Polyp Packing

zbMATH Keywords

NP-completenessgraph packingLinear-time algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Complexity of General Graph Factor Problems
• Depth-First Search and Linear Graph Algorithms
• The Factorization of Linear Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Covering Points of a Digraph with Point-Disjoint Paths and Its Application to Code Optimization
• Packings by cliques and by finite families of graphs
• On partitioning the edges of graphs into connected subgraphs
• Title not available (Why is that?)
• Packing subgraphs in a graph
• The NP-Completeness of Some Edge-Partition Problems
• On generalized matching problems
• Packings by Complete Bipartite Graphs

Cited In (20)

• On the König graphs for a 5-path and its spanning supergraphs
• Edge-disjoint packing of stars and cycles
• König graphs with respect to the 4-path and its spanning supergraphs
• An approximation algorithm for maximum \(P_{3}\)-packing in subcubic graphs
• A polynomial-time algorithm of finding a minimum \(k\)-path vertex cover and a maximum \(k\)-path packing in some graphs
• Hamiltonicity and pancyclicity of generalized prisms
• A parallel algorithm for the maximum 2-chain edge packing problem
• Approximation algorithms for the design of SDH/SONET networks
• The k‐piece packing problem
• On partial descriptions of König graphs for odd paths and all their spanning supergraphs
• Packing paths perfectly
• On the tractability of some natural packing, covering and partitioning problems
• Edge-disjoint packings of graphs
• Hamiltonicity and pancyclicity of Cartesian products of graphs
• Edge-disjoint packing of stars and cycles
• Generalized edge packings
• Complexity, algorithmic, and computational aspects of a dial-a-ride type problem
• Packing $k$-Matchings and $k$-Critical Graphs
• A remark on maximum matching of line graphs
• Fixed-parameter tractable algorithms for tracking shortest paths

This page was built for publication: Chain packing in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q808291)