Narrow Results

A work-efficient deterministic algorithm is presented for finding a maximum matching in a bipartite expander graph with any expansion factor β > 1. This improves upon a recently presented deterministic maximum matching algorithm which is restricted to those bipartite expanders with large expansion factors (β ≥ Δ^∊, ∊ > 0), and is not work-efficient [1].

The maximum dynamic contraflow problem in transportation networks seeks to maximize the flow from a source to a sink within a given time horizon with a possibility of arc reversals. This may result into blockage of paths of desired length from some node of the network towards the source. In some cases such as the evacuation planning, we may require a path towards the source to move some facilities, for example, emergency vehicles. In this work, we model the problem of saving such a path as a bicriteria optimization problem which minimizes the length of the path and maximizes the dynamic flow with arc reversals. We use the $𝜖$-constraint approach to solve the problem and propose a procedure that gives the set of all Pareto optimal solutions in a single-source-single-sink network with integer inputs. We also present computational performance of the algorithm on a road network of Kathmandu city, and on randomly generated networks. The results are of both theoretical and practical importance.

A VLSI chip is fabricated by integrating several rectangular circuit blocks on a 2D silicon floor. The circuit blocks are assumed to be placed isothetically and the netlist attached to each block is given. For wire routing, the terminals belonging to the same net are to be electrically interconnected using conducting paths. A staircase channel is an empty polygonal region on the silicon floor bounded by two monotonically increasing (or decreasing) staircase paths from one corner of the floor to its diagonally opposite corner. The staircase paths are defined by the boundaries of the blocks. In this paper, the problem of determining a monotone staircase channel on the floorplan is considered such that the number of distinct nets whose terminals lie on both sides of the channel, is minimized. Two polynomial-time algorithms are presented based on the network flow paradigm. First, the simple two-terminal net model is considered, i.e., each net is assumed to connect exactly two blocks, for which an O(n×k) time algorithm is proposed, where n and k are respectively the number of blocks and nets on the floor. Next, the algorithm is extended to the more realistic case of multi-terminal net problem. The time complexity of the latter algorithm is O((n+k)×T), where T is the total number of terminals attached to all nets in the floorplan. Solutions to these problems are useful in modeling the repeater block placement that arises in interconnect-driven floorplanning for deep-submicron VLSI physical design. It is also an important problem in context to the classical global routing, where channels are used as routing space on silicon.

Planar networks are an important special class of networks that arise in several application contexts. Because of the special structure of planar networks, network flow algorithms often run faster on these networks than they do on more general networks. In first part (Secs. 2–5), we present an algorithm for finding maximum cut and an algorithm for finding minimum flow in directed $1-n$ planar static networks with arcs and nodes capacities. This part is presented in Ciurea et al. [Proc. 5th Int. Conf. Control Decision and Information Technologies (CoDIT2018), Thessaloniki, Greece (2018), pp. 110–115]. In the second part (Secs. 6–8), we present this problem in directed $1-n$ planar dynamic networks with arcs and nodes capacities.

Bogie is one of the most major mechanical part of railway train. Its security and reliability are of paramount importance. Since research in this field is still on the early stage, which focus on either mechanical structure without condition or binary coherent systems. A multistate network flow model has been proposed in this paper with consideration of components degradation level and functional interaction between them. Firstly, the structure and function of the bogie for CRH3 were made a detailed introduction. Then transmission paths of three types force on bogie were study to determine the network strcture. Different from other papers, arcs represent the components and nodes are the transitive relation. Arc capacity tends to be confirmed easily with utilization of performance deterioration of elements on bogie involved in force tranferring. Flow rate of each arc depends on both component' health status and the task it undertakes. Furthermore, the minimal paths (MPs) method and the recursive sum of disjoint products (RSDP) with ordering heuristics are used for system reliability calculation; and the relative probability importance of each basic component and system reliability with and without forehead information are given at last. The results show that the network flow model works well on CRH3 bogie, and can support as guidance of bogie system design, daily system operation and predictive maintenance.

Live traffic flow information can help improve the efficiency of a communication network. There are many ways available to monitor the traffic flow of a network. In this paper, we propose a very efficient monitoring strategy. This strategy not only reduces the number of nodes to be monitored but also determines the complete traffic information of the entire network using the information from the monitored nodes. The strategy is optimal for monitoring a network because it reduces the number of monitored nodes to a minimum. Fast algorithms are also presented in this paper to compute the traffic information for the entire network based on the information collected from the monitored nodes. The monitoring scheme discussed in this paper can be applied to the internet, telecommunication networks, wireless ad hoc networks, large scale multiprocessor computing systems, and other information systems where the transmission of information needs to be monitored.

Using the fact that connections between vertices of a network often represent directed and weighted flows, we apply hydraulic principles to develop novel insights into network structure and growth. We develop a network model based on Bernoulli's principle and use it to analyze changes in network properties. Simulation results show that velocity of flow, resistance, fitness and existing connections in a system determine network connections of a vertex as well as overall network structure. We demonstrate how network structure is affected by changes in velocity and resistance, and how one vertex can monopolize connections within a network. Using Bernoulli's principle, we are able to independently reproduce key results in the network literature.

The occurrence of botnets over the network is crucial as it shows advent effect on various applications like finance, cyber-security, and healthcare application. Botnets are refined and more dangerous in their functionality over the network model. Most of the prevailing models and flow- and rule-based models feel challenging to predict the bot functionalities in a preventive manner. Therefore, the modeling of efficient and automated botnet detection approaches is highly essential. This research concentrates on modeling a novel botnet detection approach based on the recursively analyzing the flow of features of the network nodes spatially and temporally where the attack samples are intra-dependent time-series data. The hierarchical structural design of the network helps to integrate various levels of feature information and learns the spatial and temporal information automatically among the adjacent network connection. This process is carried out by the proposed architectural model known as Recursively Learning Long Short-Term Memory over spatial and temporal (${\mathrm{\text{RL}}}^2\text{TM-st})$. Thus, the bot activities are detected by recursively analyzing the limited number of nodes. The ${\mathrm{\text{RL}}}^2\text{TM-st})$ model is modeled to improve the efficiency of the network by eliminating unnecessary activities. The proposed model is validated using the online accessible CTU-13 dataset and benchmarked against the prevailing classification approaches for botnet detection. The simulation is done in a MATLAB environment, and the outcomes work efficiently and evaluated with prevailing models to project the significance of the ${\mathrm{\text{RL}}}^2\text{TM-st}$ model.

We study the concept of series and parallel composition of linear programming problems and show that greedy properties arc inherited by such compositions. Our results are inspired by earlier work on compositions of flow problems. We make use of certain Monge properties as well as convexity properties which support the greedy method in other contexts.

Consider a convex set in R^d and a piecewise polynomial concave function . Let be an algorithm that given a point x ∈ R^d computes F(x) if , or returns a concave polynomial p such that p(x) < 0 but for any , p(y) ≥ 0. We assume that d is fixed and that all comparisons in depend on the sign of polynomial functions of the input point. We show that under these conditions, one can find in time which is polynomial in the number of arithmetic operations of . Using our method we give the first strongly polynomial algorithms for many non-linear parametric problems in fixed dimension, such as the parametric max flow problem, the parametric minimum s-t distance, the parametric spanning tree problem and other problems. We also present an efficient algorithm for a very general convex programming problem in fixed dimension.