Ghosh, Subir Kumar ; Shermer, Thomas Caton ; Bhattacharya, Binay Kumar ; Goswami, Partha Pratim (2007) Computing the maximum clique in the visibility graph of a simple polygon Journal of Discrete Algorithms, 5 (3). pp. 524-532. ISSN 1570-8667
Full text not available from this repository.
Official URL: http://www.sciencedirect.com/science/article/pii/S...
Related URL: http://dx.doi.org/10.1016/j.jda.2006.09.004
Abstract
In this paper, we present an algorithm for computing the maximum clique in the visibility graph G of a simple polygon P in O(n2e) time, where n and e are number of vertices and edges of G respectively. We also present an O(ne) time algorithm for computing the maximum hidden vertex set in the visibility graph G of a convex fan P. We assume in both algorithms that the Hamiltonian cycle in G that corresponds to the boundary of P is given as an input along with G.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| Keywords: | Algorithm; Convexity; Convex Fan; Dynamic Programming; Hamiltonian Cycle; Hidden Vertex Set; Maximum Clique; Simple Polygon; Visibility Graph |
| ID Code: | 76284 |
| Deposited On: | 31 Dec 2011 08:58 |
| Last Modified: | 31 Dec 2011 08:58 |
Repository Staff Only: item control page
