Two-segmented channel routing is strong NP-complete

DOI10.1016/S0166-218X(97)00020-6zbMath0895.68069OpenAlexW2023228520MaRDI QIDQ1377673

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)

Related Items (8)

Two-segmented channel routing is strong NP-complete ⋮ Induced disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Induced disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Almost envy-freeness in group resource allocation ⋮ Stick graphs with length constraints ⋮ On simplified NP-complete variants of \textsc{Monotone} 3\textsc{-Sat} ⋮ Recognizing Stick Graphs with and without Length Constraints ⋮ The Monotone Satisfiability Problem with Bounded Variable Appearances

Cites Work

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

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