0478222 - ÚI 2018 GB eng J - Článek v odborném periodiku
Cabello, S. - Saumell, Maria
A randomized algorithm for finding a maximum clique in the visibility graph of a simple polygon.
Discrete Mathematics and Theoretical Computer Science. Roč. 17, č. 1 (2015), s. 1-12. ISSN 1462-7264. E-ISSN 1365-8050
Klíčová slova: visibility graph * maximum clique * simple polygon * randomized algorithm
Impakt faktor: 0.537, rok: 2015
https://dmtcs.episciences.org/2126

We present a randomized algorithm to compute a clique of maximum size in the visibility graph G of the vertices of a simple polygon P. The input of the problem consists of the visibility graph G, a Hamiltonian cycle describing the boundary of P, and a parameter delta is an element of (0, 1) controlling the probability of error of the algorithm. The algorithm does not require the coordinates of the vertices of P. With probability at least 1 delta the algorithm runs in O (vertical bar E(G)vertical bar(2)/omega(G) log(1/delta)) time and returns a maximum clique, where omega(G) is the number of vertices in a maximum clique in G. A deterministic variant of the algorithm takes O (vertical bar E(G)vertical bar(2)) time and always outputs a maximum size clique. This compares well to the best previous algorithm by Ghosh et al. (2007) for the problem, which is deterministic and runs in O(vertical bar V(G)vertical bar(2) vertical bar E(G)vertical bar) time.
Trvalý link: http://hdl.handle.net/11104/0274922