Two-segmented channel routing is strong NP-complete

DOI10.1016/S0166-218X(97)00020-6MaRDI QIDQ1377673zbMATH OpenOpenAlexFDO

Authors Wing Ning Li

Publication date 27 September 1998

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

field programmable gate arrayssegmented channel routing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1332659
• Absolute area approximation in channel routing is NP-hard
• scientific article; zbMATH DE number 140495
• Some polynomially solvable subcases of the detailed routing problem in VLSI design

Cites work

• Two-Processor Scheduling with Start-Times and Deadlines
• Two-segmented channel routing is strong NP-complete

Cited in

(13)

• scientific article; zbMATH DE number 1332659 (Why is no real title available?)
• Stick graphs with length constraints
• scientific article; zbMATH DE number 776079 (Why is no real title available?)
• Recognizing stick graphs with and without length constraints
• On simplified NP-complete variants of \textsc{Monotone 3-Sat}
• All-shortest-path 2-interval routing is NP-complete
• scientific article; zbMATH DE number 841624 (Why is no real title available?)
• Almost envy-freeness in group resource allocation
• Absolute area approximation in channel routing is NP-hard
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• The Monotone Satisfiability Problem with Bounded Variable Appearances
• Two-segmented channel routing is strong NP-complete

This page was built for publication: Two-segmented channel routing is strong NP-complete

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