English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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. Submitted: May 2014 Reviewed: July 2015 Revised: August 2015 Accepted: September 2015 Final: September 2015 Published: October 2015 Article type: Regular paper Communicated by: K. Kawarabayashi A preliminary version of this article appeared in Proceedings of the 2 International Symposium on Combinatorial Optimization (ISCO 2012), volume 7422 of Lecture Notes in Computer Science, pp. 332–343, Springer-Verlag Berlin Heidelberg, 2012. This research was funded by KAKENHI grant numbers 23500020, 25330018, 26330017, and 26540005 and The Hakubi Project at Kyoto University. E-mail addresses: asahiro@is.kyusan-u.ac.jp (Yuichi Asahiro) jj@kuicr.kyoto-u.ac.jp (Jesper Jansson) miyano@ces.kyutech.ac.jp (Eiji Miyano) hirotaka@econ.kyushu-u.ac.jp (Hirotaka Ono) 442 Asahiro et al. Graph Orientations Optimizing Light or Heavy Vertices

Graph Orientations Optimizing the Number of Light or Heavy Vertices