Skip to content

Add support for induced bipartite subgraph #145

Open
@Codsilla

Description

@Codsilla

As part of a project, I had to use bipartite induced subgraphs of a graph.

Let $G=(V,E) $ be a graph and let $X,Y\subseteq V$ such that $X \cap Y = \emptyset$. The bipartite subgraph of G induced by $X$ and $Y$ is $$(X \cup Y, X \times Y \cap E) $$
In other words, it's the bipartite subgraph made of all the edges of $G$ that are between $X$ and $Y$.
Such a construction is useful in, for example, the search of vertex separators.

I've made a simple implementation (30 lines or so) for it and I think it might be worth including it.
Before making a pull request, I wanted to see if this is something people might find interesting to have in the package.

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions