Geodesic
Graph Orientations Optimizing the Number of Light or Heavy Vertices
Journal of Graph Algorithms and Applications, Tome 19 (2015) no. 1, pp. 441-465.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

This paper introduces four graph orientation problems named MAXIMIZE W-LIGHT, MINIMIZE W-LIGHT, MAXIMIZE W-HEAVY, and MINIMIZE W-HEAVY, where W can be any fixed non-negative integer. In each problem, the input is an undirected, unweighted graph G and the objective is to assign a direction to every edge in G so that the number of vertices with outdegree at most W or at least W in the resulting directed graph is maximized or minimized. A number of results on the computational complexity and polynomial-time approximability of these problems for different values of W and various special classes of graphs are derived. In particular, it is shown that MAXIMIZE 0-LIGHT and MINIMIZE 1-HEAVY are identical to MAXIMUM INDEPENDENT SET and MINIMUM VERTEX COVER, respectively, so by allowing the value of W to vary, we obtain a new generalization of the two latter problems.
DOI : 10.7155/jgaa.00371
Keywords: graph orientation, maximum independent set, minimum vertex cover, edge packing, maximum flow 
@article{JGAA_2015_19_1_a21,
     author = {Yuichi Asahiro and Jesper Jansson and Eiji Miyano and Hirotaka Ono},
     title = {Graph {Orientations} {Optimizing} the {Number} of {Light} or {Heavy} {Vertices}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {441--465},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2015},
     doi = {10.7155/jgaa.00371},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00371/}
}
TY  - JOUR
AU  - Yuichi Asahiro
AU  - Jesper Jansson
AU  - Eiji Miyano
AU  - Hirotaka Ono
TI  - Graph Orientations Optimizing the Number of Light or Heavy Vertices
JO  - Journal of Graph Algorithms and Applications
PY  - 2015
SP  - 441
EP  - 465
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00371/
DO  - 10.7155/jgaa.00371
LA  - en
ID  - JGAA_2015_19_1_a21
ER  - 
%0 Journal Article
%A Yuichi Asahiro
%A Jesper Jansson
%A Eiji Miyano
%A Hirotaka Ono
%T Graph Orientations Optimizing the Number of Light or Heavy Vertices
%J Journal of Graph Algorithms and Applications
%D 2015
%P 441-465
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00371/
%R 10.7155/jgaa.00371
%G en
%F JGAA_2015_19_1_a21
Yuichi Asahiro; Jesper Jansson; Eiji Miyano; Hirotaka Ono. Graph Orientations Optimizing the Number of Light or Heavy Vertices. Journal of Graph Algorithms and Applications, Tome 19 (2015) no. 1, pp. 441-465. doi : 10.7155/jgaa.00371. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00371/

Cité par Sources :