PARALLEL VERTEX COLOURING OF INTERVAL GRAPHS

DOI10.1142/S0129054199000034zbMath1319.68248MaRDI QIDQ5248988

G. Sajith, Sanjeev Saxena

Publication date: 29 April 2015

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

zbMATH Keywords

graph coloring; parallel algorithm; lower bounds; graph algorithms; interval graphs; CRCW model

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68W10: Parallel algorithms in computer science

05C15: Coloring of graphs and hypergraphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

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