๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A linear time recognition algorithm for proper interval graphs

โœ Scribed by B.S. Panda; Sajal K. Das

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
128 KB
Volume
87
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

We propose a linear time recognition algorithm for proper interval graphs. The algorithm is based on certain ordering of vertices, called bicompatible elimination ordering (BCO). Given a BCO of a biconnected proper interval graph G, we also propose a linear time algorithm to construct a Hamiltonian cycle of G.

๐Ÿ“œ 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

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

A linear-time algorithm for the weighted
A linear-time algorithm for the weighted feedback vertex problem on interval graphs
โœ Chin Lung Lu; Chuan Yi Tang ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 459 KB

We present a linear-time algorithm for finding a minimum weighted feedback vertex set on interval graphs using the dynamic programming technique. Since the weighted feedback vertex problem, the weighted C3.1 problem, the maximum weighted 2-colorable subgraph problem and the maximum weighted 2-indepe