On integer network synthesis problem with tree-metric cost

DOI10.14495/JSIAML.9.73MaRDI QIDQ3121495zbMATH OpenOpenAlexFDO

Authors Hiroshi Hirai, Masashi Nitta

Publication date 18 March 2019

Published in JSIAM Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.08015

zbMATH Keywords

combinatorial optimizationnetwork synthesis problempolynomial time algorithmsplitting-offtree metric

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Abstract: Network synthesis problem (NSP) is the problem of designing a minimum-cost network (from the empty network) satisfying a given connectivity requirement. Hau, Hirai, and Tsuchimura showed that if the edge-cost is a tree metric, then a simple greedy-type algorithm solves NSP to obtain a half-integral optimal solution. This is a generalization of the classical result by Gomory and Hu for the uniform edge-cost. In this note, we present an integer version of Hau, Hirai, and Tsuchimura's result for integer network synthesis problem (INSP), where a required network must have an integer capacity. We prove that if each connectivity requirement is at least 2 and the edge-cost is a tree metrc, then INSP can be solved in polynomial time.

Recommendations

• On half-integrality of network synthesis problem
• Network synthesis with few edges
• Integer Solution to Synthesis of Communication Networks
• The network synthesis problem in a cycle
• Integer version of the multipath flow network synthesis problem

Cites work

• A Reduction Method for Edge-Connectivity in Graphs
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Connections in combinatorial optimization
• Multi-Terminal Network Flows
• On half-integrality of network synthesis problem

Cited in

(1)

• On half-integrality of network synthesis problem

This page was built for publication: On integer network synthesis problem with tree-metric cost

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