標題: FINDING A MAXIMUM SET OF INDEPENDENT CHORDS IN A CIRCLE
作者: CHANG, RC
LEE, HS
資訊工程學系
Department of Computer Science
關鍵字: CIRCLE GRAPH;COMBINATORIAL PROBLEMS;COMPUTATIONAL GEOMETRY;MAXIMUM INDEPENDENT SET;POLYGON DECOMPOSITION
公開日期: 14-二月-1992
摘要: In this note we propose an O(nm) algorithm for finding a maximum independent set of m chords which are incident to , vertices on a circle. This result can be applied to improving the time complexity of the algorithm for partitioning simple polygons into a minimum number of uniformly monotone polygons.
URI: http://dx.doi.org/10.1016/0020-0190(92)90262-T
http://hdl.handle.net/11536/3521
ISSN: 0020-0190
DOI: 10.1016/0020-0190(92)90262-T
期刊: INFORMATION PROCESSING LETTERS
Volume: 41
Issue: 2
起始頁: 99
結束頁: 102
顯示於類別:期刊論文


文件中的檔案:

  1. A1992HF69200007.pdf