Efficient Dispersion Algorithms for Geometric Intersection Graphs
作者： Peter Damaschke
关键词: Trapezoid graph 、 Chordal graph 、 Independent set 、 Metric dimension 、 Combinatorics 、 Interval graph 、 Discrete mathematics 、 Indifference graph 、 Permutation graph 、 Mathematics 、 Pathwidth
摘要: The dispersion problem in a graph requires to find subset of vertices prescribed size, so as maximize the minimum distance between chosen vertices. We propose efficient algorithms solving interval graphs, circular-arc and trapezoid graphs. Graphs are supposed be represented geometrically, rather than by their edge sets.
springer.com
sci-hub.st 参考文章(12)
B. K. Bhattacharya, M. E. Houle, Generalized Maximum Independent Sets for Trees in Subquadratic Time international symposium on algorithms and computation. pp. 435- 445 ,(1999) , 10.1007/3-540-46632-0_44
Daniel J Rosenkrantz, Giri K Tayi, SS Ravi, None, Facility dispersion problems under capacity and cost constraints Journal of Combinatorial Optimization. ,vol. 4, pp. 7- 33 ,(2000) , 10.1023/A:1009802105661
F. R. Hsu, Yaw-Ling Lin, Yin-Te Tsai, Parallel Algorithms for Shortest Paths and Related Problems on Trapezoid Graphs international symposium on algorithms and computation. pp. 173- 182 ,(1999) , 10.1007/3-540-46632-0_18
Andreas Brandstädt, Victor D. Chepoi, Feodor F. Dragan, Perfect elimination orderings of chordal powers of graphs Discrete Mathematics. ,vol. 158, pp. 273- 278 ,(1996) , 10.1016/0012-365X(95)00081-7
Carsten Flotow, On powers of circular arc graphs and proper circular arc graphs Discrete Applied Mathematics. ,vol. 69, pp. 199- 207 ,(1996) , 10.1016/0166-218X(95)00091-5
D. T. Lee, M. Sarrafzadeh, Y. F. Wu, Minimum cuts for circular-arc graphs SIAM Journal on Computing. ,vol. 19, pp. 1041- 1050 ,(1990) , 10.1137/0219071
S. Q. Zheng, Maximum independent sets of circular-arc graphs : Simplified algorithm and proofs Networks. ,vol. 28, pp. 15- 19 ,(1996) , 10.1002/(SICI)1097-0037(199608)28:1<15::AID-NET3>3.0.CO;2-G
Wen-Lian Hsu, Kuo-Hui Tsai, Linear time algorithms on circular-arc graphs Information Processing Letters. ,vol. 40, pp. 123- 129 ,(1991) , 10.1016/0020-0190(91)90165-E
Danny Z. Chen, D. T. Lee, R. Sridhar, Chandra N. Sekharan, Solving the all-pair shortest path query problem on interval and circular-arc graphs Networks. ,vol. 31, pp. 249- 258 ,(1998) , 10.1002/(SICI)1097-0037(199807)31:4<249::AID-NET5>3.0.CO;2-D
Stefan Felsner, Rudolf Müller, Lorenz Wernisch, Trapezoid graphs and generalizations, geometry and algorithms Discrete Applied Mathematics. ,vol. 74, pp. 13- 32 ,(1997) , 10.1016/S0166-218X(96)00013-3