On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems

DOI10.1002/net.21976zbMath1528.90052OpenAlexW3082445468MaRDI QIDQ6087136

Uéverton dos Santos Souza, Celina M. Herrera de Figueiredo, Alexsander A. de Melo

Publication date: 11 December 2023

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.21976

zbMATH Keywords

Steiner treedisjoint pathsconnection treeterminal verticesunitary demandmulticommodity integral flowrouter vertices

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Min-sum 2-paths problems
• Directed Steiner trees with diffusion costs
• The disjoint paths problem in quadratic time
• On shortest disjoint paths in planar graphs
• The hardness of routing two pairs on one face
• The full Steiner tree problem
• The directed subgraph homeomorphism problem
• Paths, flows, and VLSI-layout. Proceedings of a meeting held from June 20 to July 1, 1988, at the University of Bonn, Germany
• The Steiner tree problem
• Integer plane multiflows with a mixed number of demands
• The disjoint shortest paths problem
• On the terminal Steiner tree problem.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Graph minors. XIII: The disjoint paths problem
• NP-completeness of some edge-disjoint paths problems
• A multivariate analysis of the strict terminal connection problem
• On the complexity of the disjoint paths problem
• Simple undirected two-commodity integral flow with a unitary demand
• Steiner Problems with Limited Number of Branching Nodes
• Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem
• Multiflow Feasibility: An Annotated Tableau
• Disjoint paths in a network
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• On the Computational Complexity of Combinatorial Problems
• On the Complexity of Timetable and Multicommodity Flow Problems
• Shortest Two Disjoint Paths in Polynomial Time
• The steiner problem in graphs
• The edge-disjoint paths problem is NP-complete for series-parallel graphs

This page was built for publication: On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems