Strongly Connected Orientation with Minimum Lexicographic Order of Indegrees

Given a simple undirected graph G , an orientation of G is to assign every edge of G a direction. Borradaile et al gave a greedy algorithm SC-Path-Reversal (in polynomial time) which finds a strongly connected orientation that minimizes the maximum indegree, and conjectured that SC-Path-Reversal is...

Full description

Saved in:
Bibliographic Details
Published in:International journal of foundations of computer science 2022-02, Vol.33 (2), p.149-153
Main Authors: Zhou, Hongyu, Hou, Xinmin
Format: Article
Language:English
Subjects:
Greedy algorithms
Orientation
Polynomials
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a simple undirected graph G , an orientation of G is to assign every edge of G a direction. Borradaile et al gave a greedy algorithm SC-Path-Reversal (in polynomial time) which finds a strongly connected orientation that minimizes the maximum indegree, and conjectured that SC-Path-Reversal is indeed optimal for the ”minimizing the lexicographic order” objective as well. In this note, we give a positive answer to the conjecture, which is that we show that the algorithm SC-PATH-REVERSAL finds a strongly connected orientation that minimizes the lexicographic order of indegrees.
ISSN:0129-0541
1793-6373
DOI:10.1142/S0129054122500046