Search results for "Bipartite graph"
showing 10 items of 42 documents
A tabu thresholding algorithm for arc crossing minimization in bipartite graphs
1996
Acyclic directed graphs are commonly used to model complex systems. The most important criterion to obtain a readable map of an acyclic graph is that of minimizing the number of arc crossings. In this paper, we present a heuristic for solving the problem of minimizing the number of arc crossings in a bipartite graph. It consists of a novel and easier implementation of fundamental tabu search ideas without explicit use of memory structures (a tabu thresholding approach). Computational results are reported on a set of 250 randomly generated test problems. Our algorithm has been compared with the two best heuristics published in the literature and with the optimal solutions for the test proble…
An Aggressive Search Procedure for the Bipartite Drawing Problem
1996
Graphs are used to represent reality in several areas of knowledge. This has generated considerable interest in graph drawing algorithms. Arc crossing minimization is a fundamental aesthetic criterion to obtain a readable map of a graph. The problem of minimizing the number of arc crossings in a bipartite graph (BDP) is NP-complete. In this paper we present an aggressive search scheme for the BDP based on the Intensification, Diversification and Strategic Oscillation elements of Tabu Search. Several algorithms can be obtained with this scheme by implementing different evaluators in the move definitions. In this paper we propose two variants. Computational results are reported on a set of 30…
Incremental bipartite drawing problem
2001
Abstract Layout strategies that strive to preserve perspective from earlier drawings are called incremental. In this paper we study the incremental arc crossing minimization problem for bipartite graphs. We develop a greedy randomized adaptive search procedure (GRASP) for this problem. We have also developed a branch-and-bound algorithm in order to compute the relative gap to the optimal solution of the GRASP approach. Computational experiments are performed with 450 graph instances to first study the effect of changes in grasp search parameters and then to test the efficiency of the proposed procedure. Scope and purpose Many information systems require graphs to be drawn so that these syst…
Bɪ-CомDᴇт: Community Detection in Bipartite Networks
2019
Abstract Extracting hidden communities from bipartite networks witnessed a determined effort. In this respect, different streams of research relied on bipartite networks to unveil communities. In this paper, we introduce a new approach, called Bi-Comdet, that aims to an efficient community detection in bipartite networks. The main trust of the introduced approach is that it stresses on the importance of grouping two types of nodes in communities having a full connection between its nodes. The quality of the unveiled communities, is assessed through some metrics borrowed from the FCA community, to wit modularity, overlapping and stability. These metrics are then aggregated through the use of…
Entanglement dynamics and relaxation in a few-qubit system interacting with random collisions
2008
The dynamics of a single qubit interacting by a sequence of pairwise collisions with an environment consisting of just two more qubits is analyzed. Each collision is modeled in terms of a random unitary operator with a uniform probability distribution described by the uniform Haar measure. We show that the purity of the system qubit as well as the bipartite and the tripartite entanglement reach time averaged equilibrium values characterized by large instantaneous fluctuations.These equilibrium values are independent of the order of collision among the qubits. The relaxation to equilibrium is analyzed also in terms of an ensemble average of random collision histories. Such average allows for…
Bounds on mixed state entanglement
2020
In the general framework of d 1 ×
Bank-firm credit network in Japan. An analysis of a bipartite network
2015
We present an analysis of the credit market of Japan. The analysis is performed by investigating the bipartite network of banks and firms which is obtained by setting a link between a bank and a firm when a credit relationship is present in a given time window. In our investigation we focus on a community detection algorithm which is identifying communities composed by both banks and firms. We show that the clusters obtained by directly working on the bipartite network carry information about the networked nature of the Japanese credit market. Our analysis is performed for each calendar year during the time period from 1980 to 2011. Specifically, we obtain communities of banks and networks …
Bounds on the entanglement of two-qutrit systems from fixed marginals
2019
We discuss the problem of characterizing upper bounds on entanglement in a bipartite quantum system when only the reduced density matrices (marginals) are known. In particular, starting from the known two-qubit case, we propose a family of candidates for maximally entangled mixed states with respect to fixed marginals for two qutrits. These states are extremal in the convex set of two-qutrit states with fixed marginals. Moreover, it is shown that they are always quasidistillable. As a by-product we prove that any maximally correlated state that is quasidistillable must be pure. Our observations for two qutrits are supported by numerical analysis.
Higher-order Einstein-Podolsky-Rosen correlations and inseparability conditions for continuous variables
2016
We derive two types of sets of higher-order conditions for bipartite entanglement in terms of continuous variables. One corresponds to an extension of the well-known Duan inequalities from second to higher moments describing a kind of higher-order Einstein-Podolsky-Rosen (EPR) correlations. Only the second type, however, expressed by powers of the mode operators leads to tight conditions with a hierarchical structure. We start with a minimization problem for the single-partite case and, using the results obtained, establish relevant inequalities for higher-order moments satisfied by all bipartite separable states. We give an explicit example of a non-Gaussian state that exhibits fourth-orde…
Tripartite separability conditions exponentially violated by Gaussian states
2014
Starting with a set of conditions for bipartite separability of arbitrary quantum states in any dimension and expressed in terms of arbitrary operators whose commutator is a $c$-number, we derive a hierarchy of conditions for tripartite separability of continuous-variable three-mode quantum states. These conditions have the form of inequalities for higher-order moments of linear combinations of the mode operators. They enable one to distinguish between all possible kinds of tripartite separability, while the strongest violation of these inequalities is a sufficient condition for genuine tripartite entanglement. We construct Gaussian states for which the violation of our conditions grows exp…