Capacity factors in a point-to-point network

DOI10.1016/J.INS.2014.06.048zbMATH Open1355.90017arXiv1201.0435OpenAlexW2964162649MaRDI QIDQ508675FDOQ508675

Authors: Haibin Kan, Yue Zhao, Yuan Li 

Publication date: 7 February 2017

Published in: Information Sciences (Search for Journal in Brave)

Abstract: In this paper, we investigate some properties on capacity factors, which were proposed to investigate the link failure problem from network coding. A capacity factor (CF) of a network is an edge set, deleting which will cause the maximum flow to decrease while deleting any proper subset will not. Generally, a $k$-CF is a minimal (not minimum) edge set which will cause the network maximum flow decrease by $k$. Under point to point acyclic scenario, we characterize all the edges which are contained in some CF, and propose an efficient algorithm to classify. And we show that all edges on some $s$-$t$ path in an acyclic point-to-point acyclic network are contained in some 2-CF. We also study some other properties of CF of point to point network, and a simple relationship with CF in multicast network. On the other hand, some computational hardness results relating to capacity factors are obtained. We prove that deciding whether there is a capacity factor of a cyclic network with size not less a given number is NP-complete, and the time complexity of calculating the capacity rank is lowered bounded by solving the maximal flow. Besides that, we propose the analogous definition of CF on vertices and show it captures edge capacity factors as a special case.

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

Recommendations

• Network routing capacity
• Network Coding Capacity With a Constrained Number of Coding Nodes
• Network information flow
• On the capacity of information networks
• Unachievability of network coding capacity

zbMATH Keywords

NP-completenessnetwork codingcapacity factorcapacity rankmulticast network

Mathematics Subject Classification ID

Reliability, availability, maintenance, inspection in operations research (90B25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Communication networks in operations research (90B18)

Cites Work

• Introduction to algorithms
• Title not available (Why is that?)
• Conditional connectivity
• Synthesis of reliable networks - a survey
• Network information flow
• On computing a conditional edge-connectivity of a graph
• An Algebraic Approach to Link Failures Based on Network Coding
• Approximation algorithms and hardness of the \(k\)-route cut problem

Cited In (2)

• Heterogeneous graphlets-guided network embedding via Eulerian-trail-based representation
• Change in network revenue due to changes in capacities of links

This page was built for publication: Capacity factors in a point-to-point network

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