New sequential and parallel algorithms for interval graph recognition
type: Item
instance of: scholarly article
title: New sequential and parallel algorithms for interval graph recognition
zbMATH Open document ID: 0711.68084
DOI: 10.1016/0020-0190(90)90163-R
author: G. Ramalingam
author: C. Pandu Rangan
published in: Information Processing Letters
publication date: 1990-01-01T00:00:00Z
review text: The paper aims at solving the problem of recognising interval graphs and at constructing an internal representation for interval graphs. The importance of this problem arises from the fact that many NP-complete graph problems admit polynomial time solutions if the input is restricted to the class of interval graphs. The algorithm proposed by the authors can be parallelized. Step 1 takes \(O(\log^ 3(n))\) time on \(n^ 4\) processors, step 2 takes O(log(n)) time using \(O(n^ 2)\) processors and step 3 takes O(log(n)) time using \(O(n^ 2)\) processors under the CREW model.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4170127
zbMATH Keywords: interval graphs
reviewed by: Dan Grigoras
MaRDI profile type: Publication
cites work: Total domination in interval graphs
cites work: Some parallel algorithms on interval graphs
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: The edge inducibility of graphs
cites work: Finding Hamiltonian circuits in interval graphs
cites work: Q3785976
cites work: Q3732972
cites work: A unified approach to domination problems on interval graphs
cites work: Q4138414
description: scientific article; zbMATH DE number 4170127