Planar Integer Linear Programming is NC Equivalent to Euclidean GCD

DOI10.1137/S0097539794276841zbMATH Open0911.68059OpenAlexW2083566788MaRDI QIDQ4210079FDOQ4210079

Authors: David F. Shallcross, Victor Y. Pan, Yu Lin-Kriz 

Publication date: 20 September 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539794276841

Recommendations

• scientific article; zbMATH DE number 742957
• The iterated mod problem
• An ${\mathcal{N} \mathcal{C}}$ Algorithm for Evaluating Monotone Planar Circuits
• Planar graph perfect matching is in NC
• scientific article; zbMATH DE number 1254018

zbMATH Keywords

Euclidean algorithminteger linear programminggreatest common divisorparallel computational complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Distributed algorithms (68W15) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (2)

• Title not available (Why is that?)
• The iterated mod problem

This page was built for publication: Planar Integer Linear Programming is NC Equivalent to Euclidean GCD

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