Questions tagged [bipartite-graphs]

The tag has no usage guidance.

10 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
93 views

Counting matchings on 3-regular bipartite graphs

What I call a graph here allows parallel edges. Is the following problem #P-hard: INPUT: a 3-regular bipartite graph $G$ OUTPUT: the number of matchings of $G$. It is known that counting matchings ...
3
votes
0answers
224 views

Generating a random connected bipartite graph

A (n, m, k)-bipartite graph is a bipartite graphs with: independent sets of size $\{n, m\}$ a total of $k \geq n+m-1$ edges We want an algorithm to generate a (n, m, k)-bipartite selected uniformly ...
3
votes
0answers
473 views

Eigenvalues of adjacency matrix of a connected bipartite graph

Let $G=(V,E)$ is a connected d-regular bipartite graph with the same number of vertices on both sides of the bipartition. It's known that that the largest eigenvalue of its adjacency matrix would be d,...
3
votes
0answers
113 views

Is Permanent $+$-reducible?

Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$. Is ...
2
votes
0answers
58 views

Degree distribution of certain subgraphs of a biregular graph

Consider a bipartite graph $G=(X,Y)$, such that the degree of a left node $x \in X$ is $l$, and the degree of a right node $y \in Y$ is $r$. The number of edges is $|E|=|X|l=|Y|r$. Pick $w$ nodes in ...
1
vote
0answers
72 views

Alternative criterion for approximate maximum-weight perfect matching algorithms

I have asked this question in cs.stackeschange, and it was recommended to me that I asked it here. Is there any literature on approximate maximum-weight perfect matchings where the approximation ...
1
vote
0answers
104 views

Does simplex algorithm run in polynomial on Bipartite Perfect matching polytope?

It is well known that simplex algorithm runs in exponential time in worst case. However are there situations (necessary and sufficient conditions) where simplex algorithm runs in polynomial time? In ...
1
vote
0answers
104 views

algorithms for a large submatrix / general factor / quasi-biclique problem?

Given a sparse 0/1 matrix $X$, too large to fit in memory, with $m$ rows and $n$ columns, I'm looking for an algorithm for finding a submatrix (when one exists) with maximum number of rows such that ...
1
vote
0answers
100 views

Algorithm for maximum bipartite matching with arriving edges?

Given a bipartite graph with fixed nodes and incrementally arriving edges, is there any efficient algorithm to compute and update the maximum matching?
0
votes
0answers
30 views

Alternating Delivery Problem

What is known about the complexity of the following problem: Suppose we have a complete bipartite graph $G(V,E)$ with disjoint sets $C$ and $T$. The candidate vertices, and the target vertices ...