Chain packing in graphs

DOI10.1007/BF01759074MaRDI QIDQ808291zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• Covering Points of a Digraph with Point-Disjoint Paths and Its Application to Code Optimization
• Depth-First Search and Linear Graph Algorithms
• On generalized matching problems
• On partitioning the edges of graphs into connected subgraphs
• On the Complexity of General Graph Factor Problems
• Packing subgraphs in a graph
• Packings by Complete Bipartite Graphs
• Packings by cliques and by finite families of graphs
• The Factorization of Linear Graphs
• The NP-Completeness of Some Edge-Partition Problems

Cited in

(20)

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

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)