Semantic Scholar Open Access 2012 21 sitasi

Egalitarian Graph Orientations

G. Borradaile Jennifer Iglesias Theresa Migler Antonio Ochoa G. Wilfong +1 lainnya

Lihat Sumber DOI

Abstrak

Given an undirected graph, one can assign directions to each of the edges of the graph, thus orienting the graph. To be as egalitarian as possible, one may wish to find an orientation such that no vertex is unfairly hit with too many arcs directed into it. We discuss how this objective arises in problems resulting from telecommunications. We give optimal, polynomial-time algorithms for: finding an orientation that minimizes the lexicographic order of the indegrees and finding a strongly-connected orientation that minimizes the maximum indegree. We show that minimizing the lexicographic order of the indegrees is NP-hard when the resulting orientation is required to be acyclic.

Topik & Kata Kunci

Computer Science Mathematics

Penulis (6)

G. Borradaile

Jennifer Iglesias

Theresa Migler

Antonio Ochoa

G. Wilfong

Lisa Zhang

Format Sitasi

APA MLA BibTeX

Borradaile, G., Iglesias, J., Migler, T., Ochoa, A., Wilfong, G., Zhang, L. (2012). Egalitarian Graph Orientations. https://doi.org/10.7155/jgaa.00435

Akses Cepat

Lihat di Sumber doi.org/10.7155/jgaa.00435

Informasi Jurnal

Tahun Terbit: 2012
Bahasa: en
Total Sitasi: 21×
Sumber Database: Semantic Scholar
DOI: 10.7155/jgaa.00435
Akses: Open Access ✓