Search results for "Bipartite graph"
showing 10 items of 42 documents
Some complexity and approximation results for coupled-tasks scheduling problem according to topology
2016
International audience; We consider the makespan minimization coupled-tasks problem in presence of compatibility constraints with a specified topology. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same sub-tasks execution time and idle time duration. We study several problems in framework of classic complexity and approximation for which the compatibility graph is bipartite (star, chain,. . .). In such a context, we design some efficient polynomial-time approximation algorithms for an intractable scheduling problem according to some parameters.
REDUCTION OF CONSTRAINT SYSTEMS
1993
Geometric modeling by constraints leads to large systems of algebraic equations. This paper studies bipartite graphs underlaid by systems of equations. It shows how these graphs make possible to polynomially decompose these systems into well constrained, over-, and underconstrained subsystems. This paper also gives an efficient method to decompose well constrained systems into irreducible ones. These decompositions greatly speed up the resolution in case of reducible systems. They also allow debugging systems of constraints.
Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness
2016
We study space and time efficient quantum algorithms for two graph problems -- deciding whether an $n$-vertex graph is a forest, and whether it is bipartite. Via a reduction to the s-t connectivity problem, we describe quantum algorithms for deciding both properties in $\tilde{O}(n^{3/2})$ time and using $O(\log n)$ classical and quantum bits of storage in the adjacency matrix model. We then present quantum algorithms for deciding the two properties in the adjacency array model, which run in time $\tilde{O}(n\sqrt{d_m})$ and also require $O(\log n)$ space, where $d_m$ is the maximum degree of any vertex in the input graph.
Laplacian versus Adjacency Matrix in Quantum Walk Search
2015
A quantum particle evolving by Schr\"odinger's equation contains, from the kinetic energy of the particle, a term in its Hamiltonian proportional to Laplace's operator. In discrete space, this is replaced by the discrete or graph Laplacian, which gives rise to a continuous-time quantum walk. Besides this natural definition, some quantum walk algorithms instead use the adjacency matrix to effect the walk. While this is equivalent to the Laplacian for regular graphs, it is different for non-regular graphs, and is thus an inequivalent quantum walk. We algorithmically explore this distinction by analyzing search on the complete bipartite graph with multiple marked vertices, using both the Lapla…
The prime graph on class sizes of a finite group has a bipartite complement
2020
Abstract Let G be a finite group, and let cs ( G ) denote the set of sizes of the conjugacy classes of G. The prime graph built on cs ( G ) , that we denote by Δ ( G ) , is the (simple undirected) graph whose vertices are the prime divisors of the numbers in cs ( G ) , and two distinct vertices p, q are adjacent if and only if pq divides some number in cs ( G ) . A rephrasing of the main theorem in [8] is that the complement Δ ‾ ( G ) of the graph Δ ( G ) does not contain any cycle of length 3. In this paper we generalize this result, showing that Δ ‾ ( G ) does not contain any cycle of odd length, i.e., it is a bipartite graph. In other words, the vertex set V ( G ) of Δ ( G ) is covered b…
Hierarchies of geometric entanglement
2007
We introduce a class of generalized geometric measures of entanglement. For pure quantum states of $N$ elementary subsystems, they are defined as the distances from the sets of $K$-separable states ($K=2,...,N$). The entire set of generalized geometric measures provides a quantification and hierarchical ordering of the different bipartite and multipartite components of the global geometric entanglement, and allows to discriminate among the different contributions. The extended measures are applied to the study of entanglement in different classes of $N$-qubit pure states. These classes include $W$ and $GHZ$ states, and their symmetric superpositions; symmetric multi-magnon states; cluster s…
Strong monogamy of bipartite and genuine multipartite entanglement: The Gaussian case
2007
We demonstrate the existence of general constraints on distributed quantum correlations, which impose a trade-off on bipartite and multipartite entanglement at once. For all N-mode Gaussian states under permutation invariance, we establish exactly a monogamy inequality, stronger than the traditional one, that by recursion defines a proper measure of genuine N-partite entanglement. Strong monogamy holds as well for subsystems of arbitrary size, and the emerging multipartite entanglement measure is found to be scale invariant. We unveil its operational connection with the optimal fidelity of continuous variable teleportation networks.
An Efficient Algorithm for Helly Property Recognition in a Linear Hypergraph
2001
International audience; In this article we characterize bipartite graphs whose associated neighborhood hypergraphs have the Helly property. We examine incidence graphs both hypergraphs and linear hypergraphs and we give a polynomial algorithm to recognize if a linear hypergraph has the Helly property.
A tabu search algorithm for the bipartite drawing problem
1998
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 a Tabu Search (TS) scheme for the BDP. 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 300 randomly generated test problems. The two algorithms have been compared with the best heuristics…
Adaptive memory programming for the dynamic bipartite drawing problem
2020
Abstract The bipartite drawing problem is a well-known NP-hard combinatorial optimization problem with numerous applications. The aim is to minimize the number of edge crossings in a two-layer graph, in which the edges are drawn as straight lines. We consider the dynamic variant of this problem, called the dynamic bipartite drawing problem (DBDP), which consists of adding (resp. or removing) vertices and edges to (resp. or from) a given bipartite drawing, thereby obtaining a new drawing with a layout similar to that of the original drawing. To solve this problem, we propose a tabu search method that incorporates adaptive memory to search the solution space efficiently. In this study, we com…