The complexity of finding uniform emulations on paths and ring networks
From MaRDI portal
Publication:918210
DOI10.1016/0890-5401(90)90027-FzbMath0705.68062OpenAlexW1978600315WikidataQ59568073 ScholiaQ59568073MaRDI QIDQ918210
Publication date: 1990
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0890-5401(90)90027-f
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
Graph drawings with few slopes, Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation}, Two-Dimensional partitioning problems, On approximation intractability of the path-distance-width problem, A Greibach normal form for context-free graph grammars, On tree-partition-width
Cites Work
- Unnamed Item
- Unnamed Item
- The complexity of finding uniform emulations on fixed graphs
- Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
- On Some Variants of the Bandwidth Minimization Problem
- Simulation of large networks on smaller networks
- Quotient Networks
- Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
- Complexity Results for Bandwidth Minimization