Paper Info
Title
Better Decomposition Heuristics for the Maximum-Weight Connected Graph Problem Using Betweenness Centrality
Abstract
We present new decomposition heuristics for finding the optimal solution for the maximum-weight connected graph problem, which is known to be NP-hard. Previous optimal algorithms for solving the problem decompose the input graph into subgraphs using heuristics based on node degree. We propose new heuristics based on betweenness centrality measures, and show through computational experiments that our new heuristics tend to reduce the number of subgraphs in the decomposition, and therefore could lead to the reduction in computational time for finding the optimal solution. The method is further applied to analysis of biological pathway data.
Year
DOI
Venue
2009
10.1007/978-3-642-04747-3_40
Discovery Science
Keywords
Field
DocType
betweenness centrality,maximum-weight connected graph problem,optimal solution,new decomposition heuristics,betweenness centrality measure,computational time,previous optimal algorithm,new heuristics,computational experiment,better decomposition heuristics,problem decompose,input graph,computer experiment,connected graph
Graph,Mathematical optimization,Random graph,Computer science,Centrality,Heuristics,Vertex connectivity,Betweenness centrality,Connectivity,Alpha centrality
Conference
Volume
ISSN
Citations 
5808
0302-9743
3
PageRank 
References 
Authors
0.44
7
4
Name
Order
Citations
PageRank
Takanori Yamamoto1171.08
Hideo Bannai262079.87
Masao Nagasaki336826.22
Satoru Miyano42406250.71