全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

On finding orientations with fewest number of vartices with small out-degree

Full-Text   Cite this paper   Add to My Lib

Abstract:

Given an undirected graph, each of the two end-vertices of an edge can own the edge. Call a vertex poor, if it owns at most one edge. We give a polynomial time algorithm for the problem of finding an assignment of owners to the edges which minimizes the number of poor vertices. In the terminology of graph orientation, this means finding an orientation for the edges of a graph minimizing the number of edges with out-degree at most 1, and answers a question of Asahiro Jansson, Miyano, Ono (2014).

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133