Single-exception sorting networks and the computational complexity of optimal sorting network verification

DOI10.1007/BF02090767zbMath0731.68052MaRDI QIDQ3357540

Ian Parberry

Publication date: 1990

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

sorting networksorting-network verification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)

Related Items (1)

A computer-assisted optimal depth lower bound for nine-input sorting networks

Cites Work

• Sorting in \(c \log n\) parallel steps
• Strong nondeterministic Turing reduction - a technique for proving intractability
• A computer-assisted optimal depth lower bound for nine-input sorting networks
• A Sorting Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Single-exception sorting networks and the computational complexity of optimal sorting network verification