Two-segmented channel routing is strong NP-complete

DOI10.1016/S0166-218X(97)00020-6zbMATH Open0895.68069OpenAlexW2023228520MaRDI QIDQ1377673FDOQ1377673

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

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

zbMATH Keywords

field programmable gate arrayssegmented channel routing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

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

Cited In (13)

• Title not available (Why is that?)
• Stick graphs with length constraints
• Title not available (Why is that?)
• Recognizing stick graphs with and without length constraints
• On simplified NP-complete variants of \textsc{Monotone 3-Sat}
• Title not available (Why is that?)
• All-shortest-path 2-interval routing is NP-complete
• 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)