VOLUME 16 NUMBER 2 (July to December 2023)

PSL%202021 vol14-no01-p12-28-Mikita%20and%20Padlan

SciEnggJ. 2023 16 (2) 291-309
available online: August 18, 2023

*Corresponding author
Email Address: alfonso.labao@upd.edu.ph
Date received: April 2, 2023
Date revised: May 23, 2023
Date accepted: August 15, 2023

ARTICLE

Survivable Network Design with Constrained h-Subgraph Flows

Alfonso B. Labao* and Henry N. Adorna

1Department of Computer Science, College of Engineering,
     University of the Philippines, Diliman, Quezon City, 1101, Philippines

KEYWORDS: approximation algorithms; survivable network design; combinatorial optimization; graph algorithms; algorithmics

In this paper, we propose a variant of the survivable network design problem, where subgraphs are given flow constraints, which represent upper bounds on weights of outgoing edges with endpoints that belong to vertex subsets of these subgraphs. The general problem of verifying whether the weights of outgoing edges of any vertex subset (i.e. a graph cut) of an arbitrary subgraph meets a certain upper bound is a computationally hard problem. However, our proposed problem considers special types of subgraphs (termed h-subgraphs) which possess a tree structure. In particular, a h-subgraph consists of a trunk whose vertices are connected by a unique path and which are termed as trunk vertices. Each trunk vertex is connected to a branch which also has a tree structure. This special graph structure of h-subgraphs - along with conditions over the flow constraint function and additional constraints on the optimization problem allow for the construction of a polynomial-time algorithm to solve our proposed problem - using efficient separation oracles under the ellipsoid method of linear programming. Our proposed algorithm provides (2pl,2z(S)+3)-performance where p is the maximum length of any path that connects the root and leaves of a branch of any h-subgraph, l is the maximum number of leaves of any branch of a h-subgraph, and S is a vertex subset of a branch of a h-subgraph.

© 2024 SciEnggJ
Philippine-American Academy of Science and Engineering