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

DOI10.1002/NET.21976MaRDI QIDQ6087136zbMATH OpenOpenAlexFDO

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

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) Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)

Recommendations

• Simple undirected two-commodity integral flow with a unitary demand
• The hardness of routing two pairs on one face
• NP-completeness of some edge-disjoint paths problems
• On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary
• On the complexity of the planar directed edge-disjoint paths problem

Cites work

• scientific article; zbMATH DE number 4211829 (Why is no real title available?)
• scientific article; zbMATH DE number 6423757 (Why is no real title available?)
• scientific article; zbMATH DE number 7053391 (Why is no real title available?)
• A multivariate analysis of the strict terminal connection problem
• Abusing the Tutte matrix: an algebraic instance compression for the K-set-cycle problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Directed Steiner trees with diffusion costs
• Disjoint paths in a network
• Graph minors. XIII: The disjoint paths problem
• Integer plane multiflows with a mixed number of demands
• Introduction to algorithms.
• Min-sum 2-paths problems
• Multiflow Feasibility: An Annotated Tableau
• NP-completeness of some edge-disjoint paths problems
• On shortest disjoint paths in planar graphs
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the Computational Complexity of Combinatorial Problems
• On the complexity of the disjoint paths problem
• On the terminal Steiner tree problem.
• Paths, flows, and VLSI-layout. Proceedings of a meeting held from June 20 to July 1, 1988, at the University of Bonn, Germany
• Shortest two disjoint paths in polynomial time
• Simple undirected two-commodity integral flow with a unitary demand
• Steiner problems with limited number of branching nodes
• The Steiner tree problem
• The directed subgraph homeomorphism problem
• The disjoint paths problem in quadratic time
• The disjoint shortest paths problem
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• The full Steiner tree problem
• The hardness of routing two pairs on one face
• The steiner problem in graphs
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

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

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