The NP-completeness column: An ongoing gulde

DOI10.1016/0196-6774(82)90032-3MaRDI QIDQ3968457zbMATH OpenOpenAlexFDO

Authors D. 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

interconnection of points in the planerouting in graphs

Mathematics Subject Classification ID

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

Cited in

(9)

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

This page was built for publication: The NP-completeness column: An ongoing gulde

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