Vulnerability of a real-world complex network against unwanted attacks and random link failures is an issue of immense concern. A small attack or failure of the network, has the potential to trigger ...a global cascading breakdown, thereby raising questions with regard to the possible strategies to combat such a mishap. Many works have been published lately, that deals mainly with the revival of a complex network after an attack or failure. In this paper, we propose to build the network architecture in an efficient manner, so that the network can withstand attacks or link failures up to some certain pre-specified limit. We introduce a novel approach to enhance the robustness of a network from the prevention point of view, that is prior to an attack or failure. Simulation results reveal that with a slight increase in the number of driver nodes, from that obtained using the existing maximum matching algorithm, enhances the stability of the network up to a large number of link failures. We also observe that, the sparse and inhomogeneous networks are difficult to control and are less robust, compared to dense and homogeneous networks.
We propose a method for the sharing of capacity among zones of a communication network. Our approach can be employed either when a zone owner wishes to sell capacity for a specified period of time to ...a number of different zones, or when zones cooperate to build a network to be shared among themselves. We show how load balancing can be performed to mediate between rapidly fluctuating costs and the capacity of zone, which might be traded. Depending on the density of the zone, an important property of the process is that it prevents zone from congestion.
There are lots of steps and complicated calculation in the existing algorithm for solving the maximum flow,and because of improper selection order of augmented path, we cannot obtain the ideal ...maximum flow. In order to solve these problems in existing algorithm, this paper make some improvement of the existing algorithms, then puts forward a new improved algorithm for solving the maximum flow problem which make use of divide area and the degree of vertex. And it is verified that the improved algorithm is effective and intuitive through the concrete example, and avoid the labeling process, the entire operation process only needs drawing a diagram to be completed.
Heuristic for maximum matching in directed complex networks Chatterjee, Ayan; Das, Debayan; Naskar, Mrinal K. ...
2013 International Conference on Advances in Computing, Communications and Informatics (ICACCI),
2013-Aug.
Conference Proceeding
Determining maximum matching in any network has always been a problem of immense concern. Its solution is a necessary requirement in structural control theory for controlling real world complex ...networks. The prevalent classical approach through the Hopcroft-Karp algorithm and other proposed algorithms require the determination of the bipartite equivalent graph (i.e., network), which belongs to the NP-complete class of problems. In this article, we develop a degree-first greedy search algorithm to determine maximum matching in unipartite graphs without determining its bipartite equivalent. Thus this classical problem of the NP-Complete class can be solved using the heuristic, with reduced complexity. This algorithm can be efficiently used to find maximum matching in most of the real world complex networks which follow Erdos-Rényi model. Simulation results obtained using our heuristic show that dense and homogenous networks can be controlled with fewer controller nodes popularly termed as driver nodes, compared to the sparse inhomogeneous networks.
Modeling of complex physical systems with Modelica usually leads to the high-index differential algebraic equation system (DAE), index reduction is an important part of solving the high-index DAE. ...The structure index reduction algorithm is one of the popular methods, but in special cases, it fails. Combinatorial relaxation algorithm can detect and correct the breakdown situation. And the maximum weight matching of bipartite graph is an important part of the combinatorial relaxation algorithm. In order to choose the proper method for the large-scale, dense bipartite graph, this paper provides three implementations of the Hungarian algorithm. The experiment results and the theory show that the BFS single-augmented method is better than others.
This paper discusses an approach to solve the maximum matching problem in Bipartite graph (B-graph) where the graph is partially matched and the existing matches cannot be changed. It uses the ...approach of choosing vertices for matching based on the run-time weight calculation. Vertex with highest weight is given preference for matching. Weights are assigned to vertices based on its number of matched, pass-through and un-matched edges. Matching is done by choosing vertices with highest weight from both disjoint set of vertices and continuing to form an Alternative path (A-path). This approach leads to finding and traversing through maximum number of A-paths (with no shared vertex) and making maximum matching in each of those A-paths. This condition will result in a B-graph which will have the maximum possible matching. 2N-Soft-fail Sector Redundancy for Access Points is one of the applications explained in this paper.
In this work, we propose a collaborative image transmission based on shape matching over WMSN in field of monitoring. First, the SensEye's node model is utilized to lessen the transmission of ...background from the nodes. After the nodes detect a same target during shape matching, the transmission of the redundant data of the targets between nodes is eliminated. In order to reduce the delay produced by the image processing, a new assignment algorithm is proposed to solve the responding points assignment problem.
Draining Algorithm for the Maximum Flow Problem Jiyang Dong; Wei Li; Congbo Cai ...
2009 WRI International Conference on Communications and Mobile Computing,
2009-Jan., Letnik:
3
Conference Proceeding
A new augmenting path based algorithm called draining algorithm is proposed for the maximum flow problem in this letter. Unlike other augmenting path based algorithms which augment gradually the flow ...from zero-flow to the maximum flow, the proposed algorithm drains the redundant capacities out of the network to achieve the maximum flow. Experimental results shown the high efficiency of the proposed algorithm in near saturated network, thought it has a same computational complex with the traditional augmenting path approach for regular flow networks.
A matching on a graph is a set of edges, no two of which share a vertex. A maximum matching contains the greatest number of edges possible. This paper presents an efficient implementation of Edmonds' ...algorithm for finding a maximum matching. The computation time is proportional to
V
3
, where
V
is the number of vertices; previous implementations of Edmonds' algorithm have computation time proportional to
V
4
. The implementation is based on a system of labels that encodes the structure of alternating paths.
PDF