TY - GEN
T1 - Max-and min-neighborhood monopolies
AU - Makino, Kazuhisa
AU - Yamashita, Masafumi
AU - Kameda, Tiko
PY - 2000/1/1
Y1 - 2000/1/1
N2 - Given a graph G = (V,E) and a set of vertices M ⊑ V, a vertex v ϵ V is said to be controlled by M if the majority of v's neighbors (including itself) belongs to M. M is called a monopoly if every vertex v ϵ V is controlled by M. For a specified M and a range for E (E1 ⊑ E ⊑ E2), we try to determine E such that M is a monopoly in G = (V,E). We first present a polynomial algorithm for testing if such an E exists, by formulating it as a network flow problem. Assuming that a solution E does exist, we then show that a solution with the maximum or minimum |E| can be found in polynomial time, by considering them as weighted matching problems. In case there is no solution E, we want to maximize the number of vertices controlled by the given M. Unfortunately, this problem turns out to be NP-hard. We therefore design a simple approximation algorithm which guarantees an approximation ratio of 2.
AB - Given a graph G = (V,E) and a set of vertices M ⊑ V, a vertex v ϵ V is said to be controlled by M if the majority of v's neighbors (including itself) belongs to M. M is called a monopoly if every vertex v ϵ V is controlled by M. For a specified M and a range for E (E1 ⊑ E ⊑ E2), we try to determine E such that M is a monopoly in G = (V,E). We first present a polynomial algorithm for testing if such an E exists, by formulating it as a network flow problem. Assuming that a solution E does exist, we then show that a solution with the maximum or minimum |E| can be found in polynomial time, by considering them as weighted matching problems. In case there is no solution E, we want to maximize the number of vertices controlled by the given M. Unfortunately, this problem turns out to be NP-hard. We therefore design a simple approximation algorithm which guarantees an approximation ratio of 2.
UR - http://www.scopus.com/inward/record.url?scp=84956869114&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84956869114&partnerID=8YFLogxK
U2 - 10.1007/3-540-44985-X
DO - 10.1007/3-540-44985-X
M3 - Conference contribution
AN - SCOPUS:84956869114
SN - 3540676902
SN - 9783540676904
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 513
EP - 526
BT - Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings
A2 - Halldórsson, Magnús M.
PB - Springer Verlag
T2 - 7th Scandinavian Workshop on Algorithm Theory, SWAT 2000
Y2 - 5 July 2000 through 7 July 2000
ER -