• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

Ji, Sai (Ji, Sai.) | Xu, Dachuan (Xu, Dachuan.) (Scholars:徐大川) | Du, Donglei (Du, Donglei.) | Gai, Ling (Gai, Ling.)

Indexed by:

EI Scopus

Abstract:

In this paper, we consider the balanced 2-correlation clustering problem on well-proportional graphs, which has applications in protein interaction networks, cross-lingual link detection, communication networks, among many others. Given a complete graph G=(V,E) with each edge (u,v)\in E labeled by + or −, the goal is to partition the vertices into two clusters of equal size to minimize the number of positive edges whose endpoints lie in different clusters plus the number of negative edges whose endpoints lie in the same cluster. We provide a (Formula Presented)-balanced approximation algorithm for the balanced 2-correlation clustering problem on M-proportional graphs. Namely, the cost of the vertex partition (Formula Presented) returned by the algorithm is at most (Formula Presented) times the optimum solution, and (Formula Presented). © 2020, Springer Nature Switzerland AG.

Keyword:

Graph algorithms Graph theory Clustering algorithms Approximation algorithms

Author Community:

  • [ 1 ] [Ji, Sai]Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing; 100124, China
  • [ 2 ] [Xu, Dachuan]Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing; 100124, China
  • [ 3 ] [Du, Donglei]Faculty of Management, University of New Brunswick, Fredericton; NB; E3B 9Y2, Canada
  • [ 4 ] [Gai, Ling]Glorious Sun School of Business and Management, Donghua University, Shanghai; 200051, China

Reprint Author's Address:

  • [gai, ling]glorious sun school of business and management, donghua university, shanghai; 200051, china

Show more details

Related Keywords:

Related Article:

Source :

ISSN: 0302-9743

Year: 2020

Volume: 12290 LNCS

Page: 97-107

Language: English

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count: 1

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 6

Affiliated Colleges:

Online/Total:1472/10612722
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.