Data encodings and their costs

DOI10.1007/BF00288886zbMath0434.68048MaRDI QIDQ1139942

Arnold L. Rosenberg

Publication date: 1978

Published in: Acta Informatica (Search for Journal in Brave)

zbMATH Keywords

encoding of a logical data structure in a physical storage structureencoding of one graph in another

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Related Items (15)

Blocking for external graph searching ⋮ Uniform data encodings ⋮ Simulations among multidimensional Turing machines ⋮ A fast implementation of a multidimensional storage into a tree storage ⋮ Unnamed Item ⋮ Perfect Storage Representations for Families of Data Structures ⋮ A comparison of two methods of encoding arrays ⋮ Storage representations for tree-like data structures ⋮ On computing distances between leaves in a complete tree ⋮ Bounds on the costs of data encodings ⋮ Bandwidth and pebbling ⋮ Relative complexity of algebras ⋮ Minimal storage representations for binary relations ⋮ Encoding search trees in lists^† ⋮ On efficient entreeings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The NP-completeness of the bandwidth minimization problem
• Some simplified NP-complete graph problems
• Representing Graphs by Knuth Trees
• Toward a theory of encoded data structures and data translation
• Preserving Proximity in Arrays
• Space and Time Hierarchies for Classes of Control Structures and Data Structures
• Preserving average proximity in arrays
• Complexity Results for Bandwidth Minimization
• Bounds on the costs of data encodings
• Relations Among Complexity Measures
• Optimal numberings and isoperimetric problems on graphs
• Optimal Assignments of Numbers to Vertices
• One-tape, off-line Turing machine computations
• Real-Time Simulation of Multihead Tape Units

This page was built for publication: Data encodings and their costs