𝔖 Bobbio Scriptorium
✦   LIBER   ✦

AnO(m + n log n) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs

✍ Scribed by Binay K. Bhattacharya; Damon Kaller

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
338 KB
Volume
25
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

We present an algorithm to compute, in O m q n log n time, a maximum clique Ž . in circular-arc graphs with n vertices and m edges provided a circular-arc model of the graph is given. If the circular-arc endpoints are given in sorted order, the Ž . time complexity is O m . The algorithm operates on the geometric structure of the circular arcs, radially sweeping their endpoints; it uses a very simple data structure consisting of doubly linked lists. Previously, the best time bound for this problem Ž . was O m log log n q n log n , using an algorithm that solved an independent subproblem for each of the n circular arcs. By using the radial-sweep technique, we need not solve each of these subproblems independently; thus we eliminate the log log n factor from the running time of earlier algorithms. For vertex-weighted Ž circular-arc graphs, it is possible to use our approach to obtain an O m log log n q . n log n algorithm for finding a maximum-weight cliqueᎏwhich matches the best known algorithm.

📜 SIMILAR VOLUMES

An n log n Algorithm for Onlin
An n log n Algorithm for Online BDD Refinement
✍ Nils Klarlund 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 177 KB

Binary decision diagrams are in widespread use in verification systems for the canonical representation of finite functions. Here we consider multivalued BDDs, which represent functions of the form : ‫ނ‬ ª L L , where L L is a finite set of leaves. We study a rather natural online BDD refinement pro

AnO(n) Algorithm for Abelianp-Group Isom
AnO(n) Algorithm for Abelianp-Group Isomorphism and anO(n log n) Algorithm for Abelian Group Isomorphism
✍ Narayan Vikas 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 417 KB

The isomorphism problem for groups is to determine whether two finite groups are isomorphic. The groups are assumed to be represented by their multiplication tables. Tarjan has shown that this problem can be done in time O(n log n + O(1) ) for groups of cardinality n. Savage has claimed an algorithm

A Note on the Riemann Problem for Genera
A Note on the Riemann Problem for General n × n Conservation Laws
✍ Fabio Ancona; Andrea Marson 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 119 KB

We analyze the structure of the general solution of the Riemann problem for a strictly hyperbolic system of conservation laws whose characteristic fields are neither genuinely non-linear nor linearly degenerate in the sense of Lax.

The Bernstein Problem for Type (n−2,&#xa
The Bernstein Problem for Type (n−2, 2)
✍ J.Carlos Gutiérrez Fernández 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 177 KB

In a recent paper we solved the Bernstein problem in the nonregular nonexcep-Ž . tional case for the type 3, 2 . The aim of this paper it is to describe explicitly all simplicial stochastic nonexceptional nonregular nonnuclear Bernstein algebras of Ž . type n y 2, 2 . According to the Lyubich conjec

The Maximum Number of Times the Same Dis
The Maximum Number of Times the Same Distance Can Occur among the Vertices of a Convex n-gon Is O(n log n)
✍ Peter Braß; János Pach 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 70 KB

Proof. Denote by f (n) the maximum number of times the unit distance can occur among n points in convex position in the plane. Let p 1 , p 2 , ..., p n , in this cyclic order, be the vertices of a convex polygon, for which the maximum is attained. Let G denote the geometric graph obtained by connect