𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Optimal Circular Arc Representations: Properties, Recognition, and Construction

✍ Scribed by Lin Chen

Book ID
102585850
Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
335 KB
Volume
56
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

We investigate some properties of minimal interval and circular arc representations and give several optimal sequential and parallel recognition and construction algorithms. We show that, among other things, given an s_t interval or circular arc representation matrix,

deciding if the representation is minimal can be done in O(log s) time with O(stΓ‚log s) EREW PRAM processors, or in O(1) time with O(st) common CRCW PRAM processors; v constructing an equivalent minimum interval representation can be done in O(log(st)) time with O(stΓ‚log(st)) EREW PRAM processors, or in O(log tΓ‚log log t) time with O(st log log tΓ‚log t) common CRCW PRAM processors, or in O(1) time with O(st) BSR processors; v constructing an equivalent minimal circular arc representation can be done in O(st) time.

πŸ“œ SIMILAR VOLUMES

Lexicographic orientation and representa
Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
✍ Pavon Hell; Jing Huang πŸ“‚ Article πŸ“… 1995 πŸ› John Wiley and Sons 🌐 English βš– 823 KB

## Abstract We introduce a simple new technique which allows us to solve several problems that can be formulated as seeking a suitable orientation of a given undirected graph. In particular, we use this technique to recognize and transitively orient comparability graphs, to recognize and represent