Chain packing in graphs
From MaRDI portal
Publication:808291
DOI10.1007/BF01759074zbMath0731.68088OpenAlexW2006069852MaRDI QIDQ808291
Toshihide Ibaraki, Shigeru Masuyama
Publication date: 1991
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01759074
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Edge-disjoint packings of graphs ⋮ Edge-disjoint packing of stars and cycles ⋮ An approximation algorithm for maximum \(P_{3}\)-packing in subcubic graphs ⋮ Edge-Disjoint Packing of Stars and Cycles ⋮ A remark on maximum matching of line graphs ⋮ A parallel algorithm for the maximum 2-chain edge packing problem ⋮ On the König graphs for a 5-path and its spanning supergraphs ⋮ A polynomial-time algorithm of finding a minimum \(k\)-path vertex cover and a maximum \(k\)-path packing in some graphs ⋮ Complexity, algorithmic, and computational aspects of a dial-a-ride type problem ⋮ Packing $k$-Matchings and $k$-Critical Graphs ⋮ Fixed-parameter tractable algorithms for tracking shortest paths ⋮ König Graphs with Respect to the 4-Path and Its Spanning Supergraphs ⋮ Approximation algorithms for the design of SDH/SONET networks ⋮ Hamiltonicity and pancyclicity of Cartesian products of graphs ⋮ Hamiltonicity and pancyclicity of generalized prisms ⋮ On partial descriptions of König graphs for odd paths and all their spanning supergraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Packings by cliques and by finite families of graphs
- On generalized matching problems
- Packing subgraphs in a graph
- On the Complexity of General Graph Factor Problems
- Packings by Complete Bipartite Graphs
- On partitioning the edges of graphs into connected subgraphs
- The NP-Completeness of Some Edge-Partition Problems
- Covering Points of a Digraph with Point-Disjoint Paths and Its Application to Code Optimization
- Depth-First Search and Linear Graph Algorithms
- The Factorization of Linear Graphs
