The complexity of finding uniform emulations on paths and ring networks

DOI10.1016/0890-5401(90)90027-FzbMath0705.68062WikidataQ59568073 ScholiaQ59568073MaRDI QIDQ918210

Hans L. Bodlaender

Publication date: 1990

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

NP-complete; connected graph; termed emulation

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

03D15: Complexity of computation (including implicit computational complexity)

Related Items

On approximation intractability of the path-distance-width problem, Two-Dimensional partitioning problems