Some parallel algorithms on interval graphs
type: Item
instance of: scholarly article
title: Some parallel algorithms on interval graphs
zbMATH Open document ID: 0636.68087
DOI: 10.1016/0166-218X(87)90068-0
author: Alan A. Bertossi
author: Maurizio A. Bonuccelli
published in: Discrete Applied Mathematics
publication date: 1987-01-01T00:00:00Z
review text: Parallel algorithms are given for finding a maximum weighted clique, a maximum weighted independent set, a minimum clique cover, and a minimum weighted dominating set of an interval graph. Parallel algorithms are also given for finding a Hamiltonian circuit and the minimum bandwindth of a proper interval graph. The shared memory model (SMM) of parallel computers is used to obtain fast algorithms.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4037240
zbMATH Keywords: Parallel algorithms
zbMATH Keywords: interval graph
zbMATH Keywords: Hamiltonian circuit
zbMATH Keywords: minimum bandwindth
zbMATH Keywords: shared memory model
MaRDI profile type: Publication
cites work: Finding Hamiltonian circuits in proper interval graphs
cites work: Dominating Sets in Chordal Graphs
cites work: Parallel Matrix and Graph Algorithms
cites work: Parallel Scheduling Algorithms
cites work: Binary Trees and Parallel Scheduling Algorithms
cites work: Q3328583
cites work: Efficient algorithms for interval graphs and circular-arc graphs
cites work: An introduction to parallelism in combinatorial optimization
cites work: Bounds to Complexities of Networks for Sorting and for Switching
cites work: An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
cites work: The NP-completeness of the bandwidth minimization problem
cites work: Q3683547
cites work: Q4138414
description: scientific article; zbMATH DE number 4037240