On the complexity of list H-packing for sparse graph classes

DOI10.1016/J.TCS.2025.115425MaRDI QIDQ6930252zbMATH OpenFDO

Authors Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Yota Otachi, Tomohito Shirai, Akira Suzuki, Yuma Tamura, Xiao Zhou

Publication date 16 September 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115425

zbMATH Keywords

packing problemparameterized complexitysparse graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A parameterized perspective on packing paths of length two
• A partial k-arboretum of graphs with bounded treewidth
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• An Improved Parameterized Algorithm for a Generalized Matching Problem
• Approximation algorithms for the test cover problem
• Chain packing in graphs
• Complexity of Finding Embeddings in a k-Tree
• Computing independent sets in graphs with large girth
• Edge-disjoint packing of stars and cycles
• Edge-disjoint packings of graphs
• Edge-packing in planar graphs
• Generalized planar matching
• Genome Rearrangements and Sorting by Reversals
• scientific article; zbMATH DE number 3726401 (Why is no real title available?)
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• Looking at the stars
• ON DISJOINT CYCLES
• On Independent Circuits Contained in a Graph
• On maximal independent sets of vertices in claw-free graphs
• On packing 3-vertex paths in a graph
• On the Complexity of General Graph Factor Problems
• On the complexity of partitioning graphs into connected subgraphs
• On the parameterized complexity of multiple-interval graph problems
• Packing K_rs in bounded degree graphs
• Packing cycles faster than Erdős-Pósa
• Packing paths perfectly
• Packing triangles in bounded degree graphs.
• Parallel Processing and Applied Mathematics
• Parameterized algorithms
• Parameterized complexity of path set packing
• Reducibility among combinatorial problems
• Some simplified NP-complete graph problems
• The \(K_r\)-packing problem
• The path set packing problem
• The Recognition of Series Parallel Digraphs

This page was built for publication: On the complexity of list \(\mathcal{H}\)-packing for sparse graph classes

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