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 algorithmgreatest common divisorinteger linear programmingparallel computational complexity

Mathematics Subject Classification ID

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

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)

• The iterated mod problem
• scientific article; zbMATH DE number 742957 (Why is no real title available?)

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)