Skip to main content

Questions tagged [bipartite-graphs]

The tag has no usage guidance.

15 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6 votes
0 answers
215 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 ...
M.Monet's user avatar
  • 1,429
4 votes
0 answers
1k 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 ...
cglacet's user avatar
  • 141
3 votes
0 answers
144 views

On perm+1 and det+1

Given a balanced bipartite graph G and a planar graph H. We do not know the number of perfect matchings in G and we do not know the number of spanning trees in H. But assume they are at least 3 both. ...
Turbo's user avatar
  • 13k
3 votes
0 answers
1k 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,...
Devil's user avatar
  • 419
2 votes
0 answers
65 views

Is there a term for expander-like graphs that expand only large subsets?

I would like to find a bipartite graph $G(L, R)$ with the following properties/constraints: For every subset $S \subseteq R$ with $\bf{|S| \geq \alpha |R|}$, its neighborhood $\Gamma(S)$ satisfies $|\...
user2465561's user avatar
2 votes
0 answers
58 views

Is Finding an *Unbalanced* Biclique in Bipartite Graphs Hard?

In the balanced biclique in bipartite graphs (MBB) problem we are given a bipartite graph $G = (L,R,E), |L| = |R| = n$ and the goal is to find an induced subgraph of $G$, $G' = (L',R',E')$, with as ...
John's user avatar
  • 412
2 votes
0 answers
96 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 ...
prsm's user avatar
  • 29
2 votes
0 answers
69 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 ...
MJK's user avatar
  • 315
1 vote
0 answers
84 views

Development details of the Hungarian algorithm for Maximum Perfect Bipartite Matching

There are two realization forms of Hungarian algorithm. One is the original dynamic matrix, and the other is via equality subgraph. I just checked the original paper of Hungarian method by Kuhn, which ...
Shawxing Kwok's user avatar
1 vote
0 answers
360 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 ...
Turbo's user avatar
  • 13k
1 vote
0 answers
113 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 ...
DavidDLewis's user avatar
1 vote
0 answers
120 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?
Chuancong Gao's user avatar
0 votes
0 answers
38 views

Bipartite Matching with a Partition Constraint over the Vertices

Let $G = (X,Y,E)$ be a bipartite graph and let $X_1,\ldots,X_r$ be a partition of $X$. For some $i \in \{1,\ldots, r\}$ and $E' \subseteq E$ we say that constraint $X_i$ is covered by some $E'$ if ...
John's user avatar
  • 412
0 votes
0 answers
47 views

On a modular inverse graph construction

Given a balanced bipartite graph $G_1$ on $2n$ vertices on the condition $PM(G_1)\equiv1\bmod2$, an integer $i$ of size $\Omega(n\log n)$, can we find a balanced bipartite graph $G_2$ on $poly(n)$ ...
Turbo's user avatar
  • 13k
0 votes
0 answers
137 views

Error in TAOCP 4a on the bipartite graph constructed from a hypergraph

The first sentence on page 33 of Donald Knuth's The Art of Computer Programming (TAOCP) Vol. 4a reads: Furthermore, a hypergraph is equivalent to a bipartite graph with vertex set $V \cup E$ and ...
Dominic van der Zypen's user avatar