Computing the maximum clique in the visibility graph of a simple polygon

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