Parameterized complexity of path set packing

DOI10.1007/S00453-025-01329-5MaRDI QIDQ6917984zbMATH OpenFDO

Authors N. R. Aravind, Roopam Saxena

Publication date 10 October 2025

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00453-025-01329-5

zbMATH Keywords

fixed-parameter tractabilitygraph algorithmsparameterized complexitypath set packingset packing

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A faster parameterized algorithm for set packing
• A partial k-arboretum of graphs with bounded treewidth
• Algorithms – ESA 2004
• An efficient parameterized algorithm for m-set packing
• An improved kernelization algorithm for \(r\)-set packing
• Approximation algorithms for \(B _{1}\)-EPG graphs
• Approximation algorithms for intersection graphs
• Computing the independence number of intersection graphs
• Decomposition by clique separators
• Edge and vertex intersection of paths in a tree
• Edge intersection graphs of single bend paths on a grid
• Edge-intersection graphs of grid paths: the bend-number
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 1223713 (Why is no real title available?)
• scientific article; zbMATH DE number 910871 (Why is no real title available?)
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Lower bounds based on the exponential time hypothesis
• On independent set in \(B_1\)-EPG graphs
• On structural parameterizations of Hitting Set: hitting paths in graphs using 2-SAT
• On the complexity of list \(\mathcal{H}\)-packing for sparse graph classes
• On the parameterized complexity of multiple-interval graph problems
• Parameterized algorithms
• Parameterized algorithms for weighted matching and packing problems
• The edge intersection graphs of paths in a tree
• The path set packing problem
• The Rectilinear Steiner Tree Problem is NP-Complete

This page was built for publication: Parameterized complexity of path set packing

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