<p>Let $G=(V, E)$ be an undirected simple graph.</p>

<p>Is it known how to list all the maximal bipartite subgraphs of $G$, without repetitions, and with a polynomial time delay and a polynomial space complexity ? </p>

<p>(by polynomial time delay it is meant that the time spent between the outputting of any two subsequent maximal bipartite subgraphs is polynomial in $|V|$)</p>

CC BY-SA 3.0
2015-06-27T23:34:40.460Z
Is it ok if the enumeration contains duplicates? If so, this can be done by adapting enumeration of spanning trees.
Klaus Draeger
CC BY-SA 3.0
2015-06-28T18:39:20.497Z
Hi, thanks for reply. No duplicate is admitted, we aim to list all the prescribed objects exactly once.
XORwell
<ds.algorithms><graph-algorithms>
Polynomial Time Delay Enumeration of Maximal Bipartite Subgraphs
XORwell
# Polynomial Time Delay Enumeration of Maximal Bipartite Subgraphs

(Asked by: username_0 on 2015-06-27)

Let $G=(V, E)$ be an undirected simple graph.

Is it known how to list all the maximal bipartite subgraphs of $G$, without repetitions, and with a polynomial time delay and a polynomial space complexity ?

(by polynomial time delay it is meant that the time spent between the outputting of any two subsequent maximal bipartite subgraphs is polynomial in $|V|$)

**Tags:** ds.algorithms, graph-algorithms
> **Comments:**
> **username_1**: Is it ok if the enumeration contains duplicates? If so, this can be done by adapting enumeration of spanning trees.  
> **username_0**: Hi, thanks for reply. No duplicate is admitted, we aim to list all the prescribed objects exactly once.  

---

## 0 answers

