Minimum feedback arc set of m-free digraphs

Minimum feedback arc set of m-free digraphs

0.00 Avg rating0 Votes
Article ID: iaor20132358
Volume: 113
Issue: 8
Start Page Number: 260
End Page Number: 264
Publication Date: Apr 2013
Journal: Information Processing Letters
Authors: ,
Keywords: optimization
Abstract:

For a simple digraph G, let β ( G ) equ1 be the size of the smallest subset X E ( G ) equ2 such that G X equ3 has no directed cycles, and let γ ( G ) equ4 be the number of unordered pairs of nonadjacent vertices in G. A digraph G is called m‐free if G has no directed cycles of length at most m. This paper proves that β ( G ) 1 m 2 γ ( G ) equ5 for any m‐free digraph G, which generalizes some known results.

Reviews

Required fields are marked *. Your email address will not be published.