RESTRICTED TRACK ASSIGNMENT WITH APPLICATIONS

DOI10.1142/S0218195994000057MaRDI QIDQ4292529zbMATH OpenOpenAlexFDO

Authors

Publication date 8 June 1994

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0218195994000057

zbMATH Keywords

approximation algorithmcircular-arc modelNP-hardtrack assignmentVLSI layout

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Recommendations

• The k-track assignment problem
• Minimum Clique Partition Problem with Constrained Weight for Interval Graphs
• The maximum clique problem in multiple interval graphs
• The maximum clique problem in multiple interval graphs (extended abstract)
• Recognizing \(d\)-interval graphs and \(d\)-track interval graphs

Cited in

(3)

• An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
• Faster goal-oriented shortest path search for bulk and incremental detailed routing
• Faster goal-oriented shortest path search for bulk and incremental detailed routing

This page was built for publication: RESTRICTED TRACK ASSIGNMENT WITH APPLICATIONS

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