Some parallel algorithms on interval graphs (Q1098312)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some parallel algorithms on interval graphs |
scientific article |
Statements
Some parallel algorithms on interval graphs (English)
0 references
1987
0 references
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.
0 references
Parallel algorithms
0 references
interval graph
0 references
Hamiltonian circuit
0 references
minimum bandwindth
0 references
shared memory model
0 references