Boost logo

Boost Users :

Subject: Re: [Boost-users] [BGL] Separating twin vertices
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-08-13 01:18:04

On Thu, 12 Aug 2010, Shaun Jackman wrote:

> Hi,
> I have a directed graph where every vertex has a twin vertex. It is
> known ahead of time which pairs of vertices are twins. I want to remove
> as few vertices as possible from the graph such that no vertex and its
> twin is in the same connected component. Could someone suggest an
> appropriate algorithm?

Connected component or strongly connected component? I'm assuming for a
directed graph that you mean SCC. When you remove a vertex, do you also
remove its twin? Is there a relationship between an edge from A -> B and
from twin(A) -> twin(B) (or twin(B) -> twin(A)), in the sense that those
edges would need to be removed in pairs? That would be implied by needing
to remove a vertex and its twin at the same time. Do you need to remove
entire vertices, or would removing just edges be OK? Also, do you need an
exact solution or would an approximation be acceptable if an exact
algorithm was too inefficient?

-- Jeremiah Willcock

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at