Some parallel algorithms on interval graphs

DOI10.1016/0166-218X(87)90068-0zbMath0636.68087MaRDI QIDQ1098312

Alan A. Bertossi, Maurizio A. Bonuccelli

Publication date: 1987

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

Parallel algorithmsHamiltonian circuitinterval graphshared memory modelminimum bandwindth

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Related Items (17)

Parallel computation on interval graphs: algorithms and experiments ⋮ The \(k\)-neighbor, \(r\)-domination problems on interval graphs ⋮ Parallel algorithms for connectivity problems on interval graphs ⋮ Parallel algorithms for the domination problems in trapezoid graphs ⋮ Parallel circle-cover algorithms ⋮ On the domatic number of interval graphs ⋮ Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs ⋮ New sequential and parallel algorithms for interval graph recognition ⋮ Parallel algorithms on interval graphs ⋮ Parallel algorithms on circular-arc graphs ⋮ Optimal parallel algorithms for finding cut vertices and bridges of interval graphs ⋮ A parallel algorithm to generate all maximal independent sets on permutation graphs ⋮ Efficient parallel recognition of some circular arc graphs. I ⋮ A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs ⋮ Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs ⋮ Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms ⋮ O(1) QUERY TIME ALGORITHM FOR ALL PAIRS SHORTEST DISTANCES ON INTERVAL GRAPHS

Cites Work

• Finding Hamiltonian circuits in proper interval graphs
• An introduction to parallelism in combinatorial optimization
• The NP-completeness of the bandwidth minimization problem
• Binary Trees and Parallel Scheduling Algorithms
• Parallel Matrix and Graph Algorithms
• Dominating Sets in Chordal Graphs
• Efficient algorithms for interval graphs and circular-arc graphs
• Parallel Scheduling Algorithms
• An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
• Bounds to Complexities of Networks for Sorting and for Switching
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Some parallel algorithms on interval graphs