The NP-completeness column: An ongoing gulde

DOI10.1016/0196-6774(82)90032-3zbMath0502.68007OpenAlexW4236067063MaRDI QIDQ3968457

David S. Johnson

Publication date: 1982

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(82)90032-3

zbMATH Keywords

routing in graphsinterconnection of points in the plane

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem books (00A07)

Related Items

Global wire routing in two-dimensional arrays, Computing a feedback arc set using PageRank, An efficient algorithm to construct disjoint path covers of DCell networks, Effective Computation of a Feedback Arc Set Using PageRank, Minimizing the sum of diameters efficiently, A branch and bound algorithm for minimizing the number of crossing arcs in bipartite graphs, Certain NP-complete matching problems, Edge-disjoint paths in planar graphs, A near-optimal Manhattan channel router for a class of nets with the shift-right-one pattern