Planar Integer Linear Programming is NC Equivalent to Euclidean GCD

DOI10.1137/S0097539794276841MaRDI QIDQ4210079zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(2)

• scientific article; zbMATH DE number 742957 (Why is no real title available?)
• 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)