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

   
Redirigiendo al acceso original de articulo en 15 segundos...
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

       
 
Gleice Kelly Barbosa Souza, Samara Oliveira Silva Santos, André Luiz Carvalho Ottoni, Marcos Santos Oliveira, Daniela Carine Ramires Oliveira and Erivelton Geraldo Nepomuceno    
Reinforcement learning is an important technique in various fields, particularly in automated machine learning for reinforcement learning (AutoRL). The integration of transfer learning (TL) with AutoRL in combinatorial optimization is an area that requir... ver más
Revista: Algorithms

 
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

 
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

 
Songlin Tian, Ying Yang and Lei Yang    
Business intelligence (BI), as a system for business data integration, processing, and analysis, is receiving increasing attention from enterprises. Data visualization is an important feature of BI, which allows users to visually observe the distribution... ver más
Revista: Applied Sciences

 
Xuesong Jin, Huiyuan Sun and Yuhang Zhang    
This research is based on an intra-frame rate control algorithm based on the Versatile Video Coding (VVC) standard, considering that there is the phenomenon of over-allocating the bitrate of the end coding tree units (CTUs) in the bit allocation process,... ver más
Revista: Applied Sciences