Bandwidth and pebbling

DOI10.1007/BF02259908MaRDI QIDQ1838912zbMATH OpenOpenAlexFDO

Authors I. H. 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 graphsundirected graphsdirected acyclic 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)

Cites work

• scientific article; zbMATH DE number 3765164 (Why is no real title available?)
• scientific article; zbMATH DE number 3622921 (Why is no real title available?)
• scientific article; zbMATH DE number 3633714 (Why is no real title available?)
• scientific article; zbMATH DE number 3420184 (Why is no real title available?)
• A comparison of two variations of a pebble game on graphs
• An observation on time-storage trade off
• Bandwidth contrained NP-complete problems
• Bounds on the costs of data encodings
• Complete Register Allocation Problems
• Complexity Results for Bandwidth Minimization
• Data encodings and their costs
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Note on minimizing the bandwidth of sparse, symmetric matrices
• On Time Versus Space
• Space and Time Hierarchies for Classes of Control Structures and Data Structures
• The NP-completeness of the bandwidth minimization problem
• The Pebbling Problem is Complete in Polynomial Space

Cited in

(6)

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

This page was built for publication: Bandwidth and pebbling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1838912)