Polynomial algorithms to finite Veber problem for a tree network

DOI10.1016/0377-0427(91)90215-6MaRDI QIDQ1176800zbMATH OpenOpenAlexFDO

Authors A. V. Panyukov, Boris V. Pelzwerger

Publication date 25 June 1992

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-0427(91)90215-6

zbMATH Keywords

complexitypolynomial algorithmstree networkVeber problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Analysis of algorithms and problem complexity (68Q25) Applications of graph theory to circuits and networks (94C15)

Review text

This paper presents a polynomial algorithm to a finite Veber problem for a tree network, and the space and time complexity of the algorithm are estimated. For special kinds of graphs the space and time complexity can be reduced. The worked out algorithms and their computer codes can be used for synthesis and development control of oil deposit transportation and communicaton networks.

Recommendations

• scientific article; zbMATH DE number 706867
• Multicommodity flows in tree-like networks
• The generalized P‐forest problem on a tree network
• scientific article; zbMATH DE number 3864952

Cites work

• A note on two problems in connexion with graphs
• A Theorem on Boolean Matrices
• On the One-Dimensional Space Allocation Problem

Cited in

(11)

• A method for calculating the optimal variants of surface communication networks at the stage of planning investments into exploitation of an oil deposit. II
• Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
• A polynomial algorithm for deciding the validity of an electrical distribution tree
• Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree
• On the existence of an integer solution to the relaxed Weber problem for a tree network
• Algorithm for the discrete Weber's problem with an accuracy estimate
• scientific article; zbMATH DE number 706867 (Why is no real title available?)
• A polynomial algorithm for thep-centdian problem on a tree
• Polynomial algorithms for the synthesis of bounded nets
• scientific article; zbMATH DE number 7310231 (Why is no real title available?)
• Solving a maximin location problem on the plane with given accuracy

Describes a project that uses

Uses Software

• Algorithm 97

This page was built for publication: Polynomial algorithms to finite Veber problem for a tree network

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