𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A linear time algorithm to recognize circular permutation graphs

✍ Scribed by Sritharan, R.

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
368 KB
Volume
27
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

An undirected graph G is a circular permutation graph if it can be represented by the following intersectiori model: Each vertex of G corresponds to a chord in the annular region between two concentric circles, and two vertices are adjacent in G if and only if their corresponding chords intersect each other exactly once. Circular perniutation graphs are a generalization of permutation graphs. Rotem and Urrutia introduced and characterized thlis class of graphs and their characterization yields an O(n' 376) algorithm for recognizing circular permutation graphs. Gardner gave an O(n2) recognition algorithm. We provide an alternate characterization and show that (an O(m t n ) recognition algorithm can be derived from the new Characterization. Our algorithm also constructs the intersection model when the input graph is a circular permutation graph (CPG).

πŸ“œ SIMILAR VOLUMES

A Simple Linear Time Algorithm for Prope
A Simple Linear Time Algorithm for Proper Box Rectangular Drawings of Plane Graphs
✍ Xin He πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 219 KB

In this paper we introduce a new style of drawing a plane graph G, called proper Ε½ . box rectangular PBR drawing. It is defined to be a drawing of G such that every vertex is drawn as a rectangle, called a box, each edge is drawn as either a horizontal or a vertical line segment, and each face is dr

A linear-time algorithm for connectedr-d
A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
✍ BrandstοΏ½dt, Andreas; Dragan, Feodor F. πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 83 KB πŸ‘ 1 views

A distance-hereditary graph is a connected graph in which every induced path is isometric, i.e., the distance of any two vertices in an induced path equals their distance in the graph. We present a linear time labeling algorithm for the minimum cardinality connected r-dominating set and Steiner tree

A simple linear time algorithm for findi
A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone
✍ Glenn K. Manacher; Terrance A. Mankus πŸ“‚ Article πŸ“… 2002 πŸ› John Wiley and Sons 🌐 English βš– 209 KB πŸ‘ 1 views

## Abstract We exhibit an algorithm for finding a maximum independent set (MIS) for __n__ presorted, unweighted circular arcs in time 0(__n__). Unlike previous algorithms, this is achieved by means of trivial postprocessing of the output of a straightforward algorithm for finding an MIS for a set o