A. V. Gavrikov, “Optimal Eulerian modification of digraphs by addition of arcs”, Izv. Saratov Univ. Math. Mech. Inform., 2012, Volume 12, Issue 1,Pages <nobr>102

Computer science

Optimal Eulerian modification of digraphs by addition of arcs

A. V. Gavrikov

Saratov State University, Chair of the Theoretical Foundations of Computer Security and Cryptography

Abstract: Тhe following problem is solved: given a directed graph, it is necessary to add to it a minimal number of arcs to obtain an Eulerian directed graph.

Key words: graph theory, Eulerian graphs, modification of digraphs, transport network, min-cost-max-flow, addition of arch.

UDC: 519.1

DOI: 10.18500/1816-9791-2012-12-1-102-109