Bandwidth and pebbling

DOI10.1007/BF02259908zbMath0509.90100OpenAlexW177441241MaRDI QIDQ1838912

Ivan Hal Sudborough, Arnold L. Rosenberg

Publication date: 1983

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02259908

zbMATH Keywords

games on graphsdirected acyclic graphsundirected graphsNP- completenessbandwidth of a graphbreadth-first pebble gamecomputational pebble game

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Positional games (pursuit and evasion, etc.) (91A24)

Related Items

Min Cut is NP-complete for edge weighted trees ⋮ Maximum vertex occupation time and inert fugitive: Recontamination does help ⋮ Searching and pebbling ⋮ Lower bounds on treespan ⋮ Complete problems for space bounded subclasses of NP ⋮ Topological Bandwidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Data encodings and their costs
• A comparison of two variations of a pebble game on graphs
• An observation on time-storage trade off
• The NP-completeness of the bandwidth minimization problem
• Bandwidth contrained NP-complete problems
• Note on minimizing the bandwidth of sparse, symmetric matrices
• The Pebbling Problem is Complete in Polynomial Space
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Complete Register Allocation Problems
• Space and Time Hierarchies for Classes of Control Structures and Data Structures
• On Time Versus Space
• Complexity Results for Bandwidth Minimization
• Bounds on the costs of data encodings