Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space

DOI10.1016/0020-0190(94)90030-2zbMath0793.68079OpenAlexW2079048332MaRDI QIDQ1318772

Sanjeev Saxena

Publication date: 4 April 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)90030-2

zbMATH Keywords

computational complexityconnected componentsparallel algorithmslinked list\(NC^ 1\)2- colouring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items (2)

Counting quantifiers, successor relations, and logarithmic space ⋮ PARALLEL VERTEX COLOURING OF INTERVAL GRAPHS

Cites Work

• Unnamed Item
• Unnamed Item
• Faster optimal parallel prefix sums and list ranking
• Erratum and addendum to: parallel computation and conflicts in memory access
• Constant Depth Reducibility
• Efficient VLSI Networks for Parallel Processing Based on Orthogonal Trees
• A taxonomy of problems with fast parallel algorithms
• An Efficient Parallel Biconnectivity Algorithm
• Problems complete for deterministic logarithmic space
• Parallel Merge Sort
• Bounds to Complexities of Networks for Sorting and for Switching
• Expressibility and Parallel Complexity
• Correction: Parallel Merge Sort
• Optimal bounds for decision problems on the CRCW PRAM

This page was built for publication: Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space