Title :
Feedback Arc Set in Oriented Graphs
Author :
Rajasingh, Indra ; Rajan, Bharati ; Joice, Little
Author_Institution :
Dept. of Math., Loyola Coll., Chennai, India
Abstract :
A feedback arc set in a directed graph D is a set S of arcs in D such that D S is acyclic. The problem of determining a feedback arc set with least number of arcs is NP - complete for a general digraph. We define the strong feedback arc number ßs(G) for various orientations of an undirected graph G. The strong feedback arc problem of an undirected graph is to find a strong feedback arc set S of G(O) for some strongly oriented O(G) such that |S|=ßs (G) . In this paper our focus is on interconnection networks with ßs=1.
Keywords :
directed graphs; optimisation; set theory; state feedback; NP-complete problem; feedback arc set; strong feedback arc problem; undirected graph; Circuit synthesis; Educational institutions; Flow graphs; Mathematics; Multiprocessor interconnection networks; Operating systems; Optical feedback; Polynomials; Resource management; Terminology;
Conference_Titel :
Computer Technology and Development, 2009. ICCTD '09. International Conference on
Conference_Location :
Kota Kinabalu
Print_ISBN :
978-0-7695-3892-1
DOI :
10.1109/ICCTD.2009.215
