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

DOI10.1016/0020-0190(94)90030-2MaRDI QIDQ1318772zbMATH OpenOpenAlexFDO

Authors 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

2- colouring\(NC^ 1\)computational complexityconnected componentslinked listparallel algorithms

Mathematics Subject Classification ID

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

Review text

It is shown that the problem of 2-colouring a linked list is complete for deterministic log-space under \(NC^ 1\) reductions.

Cites work

• A taxonomy of problems with fast parallel algorithms
• An Efficient Parallel Biconnectivity Algorithm
• Bounds to Complexities of Networks for Sorting and for Switching
• Constant Depth Reducibility
• Correction: Parallel Merge Sort
• Efficient VLSI Networks for Parallel Processing Based on Orthogonal Trees
• Erratum and addendum to: parallel computation and conflicts in memory access
• Expressibility and Parallel Complexity
• Faster optimal parallel prefix sums and list ranking
• scientific article; zbMATH DE number 4090816 (Why is no real title available?)
• scientific article; zbMATH DE number 17533 (Why is no real title available?)
• Optimal bounds for decision problems on the CRCW PRAM
• Parallel Merge Sort
• Problems complete for deterministic logarithmic space

Cited in

(2)

• Counting quantifiers, successor relations, and logarithmic space
• Parallel vertex colouring of interval graphs

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

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