Edge-Cuts of Optimal Average Weights

Scott Payne (), Edgar Fuller () and Cun-Quan Zhang
Additional contact information
Scott Payne: Department of Mathematics, West Virginia University, Morgantown, WV 28506, USA
Edgar Fuller: Department of Mathematics, Florida International University, Miami, FL 33199, USA
Cun-Quan Zhang: Department of Mathematics, West Virginia University, Morgantown, WV 28506, USA

Asia-Pacific Journal of Operational Research (APJOR), 2019, vol. 36, issue 02, 1-9

Abstract: Let G be a directed graph associated with a weight w : E(G) → R+. For an edge-cut Q of G, the average weight of Q is denoted and defined as wave(Q) = ∑e∈Qw(e) |Q|. An optimal edge-cut with average weight is an edge-cut Q such that wave(Q) is maximum among all edge-cuts (or minimum, symmetrically). In this paper, a polynomial algorithm for this problem is proposed for finding an optimal edge-cut in a rooted tree separating the root and the set of all leafs. This algorithm enables us to develop an automatic clustering method with more accurate detection of community output.

Keywords: Optimal edge-cut; average weight; algorithm; clustering; community selection (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595919400062
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:36:y:2019:i:02:n:s0217595919400062

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595919400062

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().