𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A matrix characterization of interval and proper interval graphs

✍ Scribed by George B. Mertzios

Publisher
Elsevier Science
Year
2008
Tongue
English
Weight
266 KB
Volume
21
Category
Article
ISSN
0893-9659

No coin nor oath required. For personal study only.

✦ Synopsis

In this work a matrix representation that characterizes the interval and proper interval graphs is presented, which is useful for the efficient formulation and solution of optimization problems, such as the k-cluster problem. For the construction of this matrix representation every such graph is associated with a node versus node zero-one matrix. In contrast to representations used in most of the previous work, the proposed matrix characterization does not make use of the maximal cliques in the graph investigated.

πŸ“œ SIMILAR VOLUMES

A new characterization of proper interva
A new characterization of proper interval graphs
✍ Zygmunt Jackowski πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 379 KB

One of the first characterizations of interval graphs, given by Lekkerkerker and Boland (1962), uses the concept of an asteroidal triple. In this paper we give a similar characterization on the proper interval graphs using the akin concept of an astral triple.

A relationship between triangulated grap
A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
✍ Dale J. Skrien πŸ“‚ Article πŸ“… 1982 πŸ› John Wiley and Sons 🌐 English βš– 319 KB πŸ‘ 1 views

## Abstract Given a set __F__ of digraphs, we say a graph __G__ is a __F__‐__graph__ (resp., __F__\*‐__graph__) if it has an orientation (resp., acyclic orientation) that has no induced subdigraphs isomorphic to any of the digraphs in __F__. It is proved that all the classes of graphs mentioned in

Metric characterizations of proper inter
Metric characterizations of proper interval graphs and tree-clique graphs
✍ Gutierrez, M.; OubiοΏ½a, L. πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 393 KB πŸ‘ 2 views

A connected graph G is a tree-clique graph if there exists a spanning tree T (a compatible tree) such that every clique of G is a subtree of T. When Tis a path the connected graph G is a proper interval graph which is usually defined as intersection graph of a family of closed intervals of the real

On partitioning interval graphs into pro
On partitioning interval graphs into proper interval subgraphs and related problems
✍ FrΓ©dΓ©ric Gardi πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 164 KB

In this paper, we establish that any interval graph (resp. circulararc graph) with n vertices admits a partition into at most log 3 n (resp. log 3 n +1) proper interval subgraphs, for n>1. The proof is constructive and provides an efficient algorithm to compute such a partition. On the other hand, t

A linear time recognition algorithm for
A linear time recognition algorithm for proper interval graphs
✍ B.S. Panda; Sajal K. Das πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 128 KB

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