Top

Journal of Combinatorial Optimization

Published in:

01-10-2016

Packing feedback arc sets in reducible flow graphs

Author: Han Xiao

Published in: Journal of Combinatorial Optimization | Issue 3/2016

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper we establish a min–max relation in arc-weighted reducible flow graphs. In particular, we prove that the maximum cardinality of feedback arc set packings equals the minimum total weight of cycles. We also present an \(O(n^2 m)\) algorithm for finding a maximum feedback arc set packing in reducible flow graphs.

previous article Maximum size of digraphs with some parameters

next article A diagnosis algorithm by using graph-coloring under the PMC model

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

‘First available’ here refers to the unused \(r-t\) cut \(\partial ^+(U_i)\) with the least index i.

Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows—theory, algorithms, and applications. Prentice Hall Inc., Englewood CliffsMATH

Chen X, Zang W (2006) An efficient algorithm for finding maximum cycle packings in reducible flow graphs. Algorithmica 44(3):195–211MathSciNetCrossRefMATH

Frank A, Gyarfas A (1976) Directed graphs and computer programs. Problemes Combinatoires et Theorie des Graphes 260:157–158MATH

Hecht MS (1977) Flow analysis of computer programs. North-Holland, New YorkMATH

Hecht MS, Ullman JD (1972) Flow graph reducibility. SIAM J Comput 1(2):188–202MathSciNetCrossRefMATH

Hecht MS, Ullman JD (1974) Characterizations of reducible flow graphs. J Assoc Comput Mach 21(3):367–375MathSciNetCrossRefMATH

Hopcroft JE, Ullman JD (1972) An \(n\log n\) algorithm for detecting reducible graphs. In: Proceedings of 6th Annual Princeton Conference on Information Sciences and Systems, pp. 119–122. Princeton, NJ

Ramachandran V (1988) Finding a minimum feedback arc set in reducible flow graphs. J Algorithms 9(3):299–313MathSciNetCrossRefMATH

Ramachandran V (1990) A minimax arc theorem for reducible flow graphs. SIAM J Discret Math 3(4):554–560MathSciNetCrossRefMATH

Shamir A (1979) A linear time algorithm for finding minimum cutsets in reducible graphs. SIAM J Comput 8(4):645–655MathSciNetCrossRefMATH

Tarjan RE (1974) Testing flow graph reducibility. J Comput Syst Sci 9(3):355–365MathSciNetCrossRefMATH

Title: Packing feedback arc sets in reducible flow graphs
Author: Han Xiao
Publication date: 01-10-2016
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 3/2016
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-015-9922-6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 3/2016

Equitable colorings of Cartesian products of square of cycles and paths with complete bipartite graphs

The extremal spectral radii of -uniform supertrees

On strongly planar not-all-equal 3SAT

A combinatorial proof for the circular chromatic number of Kneser graphs

Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval

A -choosable theorem on planar graphs

Premium Partner