PARALLEL VERTEX COLOURING OF INTERVAL GRAPHS

DOI10.1142/S0129054199000034zbMath1319.68248MaRDI QIDQ5248988

Sanjeev Saxena, G. Sajith

Publication date: 29 April 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

graph coloringparallel algorithmlower boundsgraph algorithmsinterval graphsCRCW model

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Parallel algorithms in computer science (68W10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Parallel Algorithms for Colouring Vertices of Graph Using Bit Manipulation

Cites Work

• Unnamed Item
• Highly parallelizable problems on sorted intervals
• Deterministic parallel list ranking
• Parallel computation and conflicts in memory access
• Optimal parallel time bounds for the maximum clique problem on intervals
• Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space
• Problems complete for deterministic logarithmic space
• Finding the maximum, merging, and sorting in a parallel computation model
• Parallelism in Comparison Problems
• Expressibility and Parallel Complexity
• Optimal Doubly Logarithmic Parallel Algorithms Based On Finding All Nearest Smaller Values
• The Parallel Simplicity of Compaction and Chaining
• Fast Deterministic Processor Allocation