Greedy Cycle Removal ( GreedyCycleRemoval )

Baseclasses

Definition

The module GreedyCycleRemoval computes a maximal acyclic subgraph G' = (V, E) of a directed input graph G = (V, E $\cup$ F). Or in other words, it computes a feedback set F of G. If G contains no self-loops, then we can obtain an acyclic graph from G by reversing all the edges in F.

The algorithm [EL95] is also described in [DETT99]. If G is a connected digraph with n vertices, m edges and no two-cycles, the algorithms guarantees that | E| > = m/2 - n/6.

General Information

Algorithm
name	Greedy Cycle Removal
long name	Greedy Cycle Removal
author

Implementation
author	C. Gutwenger
date	Decembre 1998
version	1.0

Pre- and Postcondition

precondition	=	{directed}
postcondition(PRE)	=	{maximalacyclic, directed}

#include < AGD/GreedyCycleRemoval.h >

Creation

GreedyCycleRemoval

S

creates an instance S of type GreedyCycleRemoval.

Operations

Standard Interface (Inherited Methods) The detailed description of these methods can be found in the manual entries of the base class (SubgraphModule).

bool	S.check(const graph& G, AgdKey& p)
bool	S.call(const graph& G, list<edge>& L)
bool	S.call(graph& G)
bool	S.call(GraphCopy& G, list<edge>& L)
int	S.num_del_edges()

Implementation

The computation of the subgraph takes time $\protectO$(n + m), where G is a graph with n vertices and m edges.