DTCPP - A HEURISTIC PROGRAM FOR TESTING DECYCLIZATION IN DIRECTED GRAPHS AND ITS ISOMORPHIC IMAGE BY USING COMBINATORIAL APPROACH

Madhu Tiwari (India), Jitendra Binwal (India) and C. L. Parihar (India)

Received January 8, 2009

Abstract

Given a weighted directed graph  the minimum feedback arc set problem consists of finding a minimum weight set of arcs  such that the directed graph  is acyclic. Similarly, the minimum feedback vertex set problem consists of finding a minimum weight set of vertices containing at least one vertex for each directed cycle. In this paper, we have developed a generalized heuristic program DTCPP (decyclization through C+ +) [17] for decyclization of weighted directed graphs by using simple combinatorial algorithms [5].

Keywords and phrases: feedback problems, directed graphs, combinatorial optimization, approximation algorithms, DTCPP.