Acceso al sitio web del Consejo de Políticas de Infraestructura

   
ARTÍCULO
TITULO

An improvement for an algorithm for finding a minimum feedback arc set for planar graphs

Candido Ferreira Xavier de Mendonça Neto    
Peter Eades (Author)    

Resumen

Given a directed graph G, a covering is a subset B of arcs which meets all directed cuts of G. Equivalently, the contraction of the elements of B makes G strongly connected. An O(n5) primal-dual algorithm is presented by Frank (1981) for finding a minimum covering of a directed graph. For a planar graph, the dual problem is to find a minimum set of arcs whose removal makes G acyclic. The dual problem may be solved with Frank's algorithm. Further, some improvements that may be used to make such algorithm faster in practical cases are prescuted.

PÁGINAS
pp. 841 - 845

 Artículos similares

       
 
Jianying Wei, Yuming Liu, Xiaochun Lu, Yu Feng and Yadi Wang    
Tunnel construction projects are a classic type of repetitive project, and hold a crucial position in the construction industry. The linear scheduling method (LSM) has been in the spotlight in scheduling optimization for repetitive construction projects ... ver más
Revista: Applied Sciences

 
Vedat Dogan and Steven Prestwich    
In a multi-objective optimization problem, a decision maker has more than one objective to optimize. In a bilevel optimization problem, there are the following two decision-makers in a hierarchy: a leader who makes the first decision and a follower who r... ver más
Revista: Algorithms

 
Zhou Fang, Xiaoyong Wang, Liang Zhang and Bo Jiang    
Currently, deep learning is extensively utilized for ship target detection; however, achieving accurate and real-time detection of multi-scale targets remains a significant challenge. Considering the diverse scenes, varied scales, and complex backgrounds... ver más

 
Tao Tang, Yuting Cui, Rui Feng and Deliang Xiang    
With the development of deep learning in the field of computer vision, convolutional neural network models and attention mechanisms have been widely applied in SAR image target recognition. The improvement of convolutional neural network attention in exi... ver más
Revista: Information

 
Jinghua Li, Yidong Chen, Lei Zhou, Ruipu Dong, Wenhao Yin, Wenhao Huang and Fan Zhang    
In the context of increasingly competitive shipbuilding, the flexible multi-level picking system, composed of high-rise shelves, Automated Guided Vehicles (AGVs), and picking stations, has been of gradual interest because of its advantages in operation e... ver más
Revista: Applied Sciences