The parameterised complexity of integer multicommodity flow

DOI10.4230/LIPICS.IPEC.2023.6MaRDI QIDQ6926204zbMATH OpenFDO

Authors Hans L. Bodlaender, Isja Mannens, Jelle J. Oostveen, Sukanya Pandey, Erik Jan van Leeuwen

Publication date 24 September 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2023.6

zbMATH Keywords

multicommodity flowparameterised complexityXALP-completenessXNLP-completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Cites work

• A primal-dual Algorithm for multicommodity flows and multicuts in treewidth-2 graphs
• An application of simultaneous diophantine approximation in combinatorial optimization
• Combinatorial optimization. Theory and algorithms
• Faster approximation schemes for fractional multicommodity flow problems
• Finding edge-disjoint paths in partial \(k\)-trees
• Graph minors. XIII: The disjoint paths problem
• scientific article; zbMATH DE number 3917707 (Why is no real title available?)
• scientific article; zbMATH DE number 16298 (Why is no real title available?)
• scientific article; zbMATH DE number 7764095 (Why is no real title available?)
• Multicommodity network flows: a survey. I: Applications and formulations
• Multicommodity network flows: A survey. II: Solution methods
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• New algorithms for maximum disjoint paths based on tree-likeness
• On a Problem of Sidon in Additive Number Theory, and on some Related Problems
• On space efficiency of algorithms working on structural decompositions of graphs
• On structural parameterizations of the edge disjoint paths problem
• On the complexity of problems on tree-structured graphs
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the parameterized complexity of computing tree-partitions
• On the parameterized complexity of multiple-interval graph problems
• On the space and circuit complexity of parameterized problems: classes and completeness
• Parameterized problems complete for nondeterministic FPT time and logarithmic space
• Problems hard for treewidth but easy for stable gonality
• Reducibility among combinatorial problems
• The directed subgraph homeomorphism problem
• The disjoint paths problem in quadratic time
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• The inapproximability of maximum single-sink unsplittable, priority and confluent flow problems
• The power of cut-based parameters for computing edge-disjoint paths
• XNLP-completeness for parameterized problems on graphs with a linear structure

Cited in

(5)

• On the parameterized complexity of computing tree-partitions
• XNLP-hardness of parameterized problems on planar graphs
• XALP-completeness of parameterized problems on planar graphs
• Does subset sum admit short proofs?
• Concurrency constrained scheduling with tree-like constraints

This page was built for publication: The parameterised complexity of integer multicommodity flow

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