Some parallel algorithms on interval graphs

DOI10.1016/0166-218X(87)90068-0MaRDI QIDQ1098312zbMATH OpenFDO

Authors Alan A. Bertossi, Maurizio A. Bonuccelli

Publication date 1987

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

zbMATH Keywords

interval graphHamiltonian circuitParallel algorithmsshared memory modelminimum bandwindth

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 123468
• scientific article; zbMATH DE number 3892606
• Designing efficient parallel algorithms on interval graphs
• A parllel algorithm for finding a maximum weight clique of an interval graph
• Parallel algorithms on circular-arc graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3905859 (Why is no real title available?)
• scientific article; zbMATH DE number 3566474 (Why is no real title available?)
• An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
• An introduction to parallelism in combinatorial optimization
• Binary Trees and Parallel Scheduling Algorithms
• Bounds to Complexities of Networks for Sorting and for Switching
• Dominating Sets in Chordal Graphs
• Efficient algorithms for interval graphs and circular-arc graphs
• Finding Hamiltonian circuits in proper interval graphs
• Parallel Matrix and Graph Algorithms
• Parallel Scheduling Algorithms
• The NP-completeness of the bandwidth minimization problem

Cited in

(24)

• Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs
• A parallel algorithm to generate all maximal independent sets on permutation graphs
• Parallel algorithms on interval graphs
• New sequential and parallel algorithms for interval graph recognition
• Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
• Efficient parallel recognition of some circular arc graphs. I
• Parallel algorithms on circular-arc graphs
• Optimal parallel algorithms for finding cut vertices and bridges of interval graphs
• O(1) QUERY TIME ALGORITHM FOR ALL PAIRS SHORTEST DISTANCES ON INTERVAL GRAPHS
• Parallel computation on interval graphs: algorithms and experiments
• Parallel circle-cover algorithms
• Parallel algorithms for the domination problems in trapezoid graphs
• Designing efficient parallel algorithms on interval graphs
• Recognizing and representing proper interval graphs in parallel using merging and sorting
• Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs
• Optimal sequential and parallel algorithms for computing the diameter and the center of an interval graph
• Parallel algorithms for connectivity problems on interval graphs
• scientific article; zbMATH DE number 123468 (Why is no real title available?)
• scientific article; zbMATH DE number 3892606 (Why is no real title available?)
• On the domatic number of interval graphs
• Deferred-query: An efficient approach for some problems on interval graphs
• Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms
• A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs
• The \(k\)-neighbor, \(r\)-domination problems on interval graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1098312)