×

zbMATH — the first resource for mathematics

DTCPP - A heuristic program for testing decyclization in directed graphs and its isomorphic image by using combinatorial approach. (English) Zbl 1180.05114
Summary: Given a weighted directed graph \(G=(V,E)\) the minimum feedback arc set problem consists of finding a minimum weight set of arcs \(E^{\prime}\subseteq E\) such that the directed graph \((V,E/E^{\prime})\) 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].
MSC:
05C85 Graph algorithms (graph-theoretic aspects)
05-04 Software, source code, etc. for problems pertaining to combinatorics
05C20 Directed graphs (digraphs), tournaments
68R10 Graph theory (including graph drawing) in computer science
Software:
DTCPP
PDF BibTeX XML Cite
Full Text: Link