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

DOI10.1002/NET.21976zbMATH Open1528.90052OpenAlexW3082445468MaRDI QIDQ6087136FDOQ6087136

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

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

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)

Cites Work

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

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)