SOFSEM 2011: Theory and Practice of Computer Science: 37th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 22-28, 2011. Proceedings

Front Matter....Pages -
Integrity and Consistency for Untrusted Services....Pages 1-14
A Structured Codesign Approach to Many-Core Architectures for Embedded Systems....Pages 15-25
SIMPL Systems, or: Can We Design Cryptographic Hardware without Secret Key Information?....Pages 26-45
Verification of Timed-Arc Petri Nets....Pages 46-72
Efficient Algorithms for Handling Nondeterministic Automata....Pages 73-73
The Straight-Line RAC Drawing Problem Is NP-Hard....Pages 74-85
Tracking the Evolution of Code Clones....Pages 86-98
Liquidsoap: A High-Level Programming Language for Multimedia Streaming....Pages 99-110
Combining Traditional Map Labeling with Boundary Labeling....Pages 111-122
On Making a Distinguished Vertex Minimum Degree by Vertex Deletion....Pages 123-134
Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size....Pages 135-145
GreedyMAX-type Algorithms for the Maximum Independent Set Problem....Pages 146-156
Sequential Optimization of Matrix Chain Multiplication Relative to Different Cost Functions....Pages 157-165
One-Reversal Counter Machines and Multihead Automata: Revisited....Pages 166-177
Collisionless Gathering of Robots with an Extent....Pages 178-189
Min-Max Coverage in Multi-interface Networks....Pages 190-201
Bandwidth Constrained Multi-interface Networks....Pages 202-213
A Privacy-Preserving ID-Based Group Key Agreement Scheme Applied in VPAN....Pages 214-225
White Space Regions....Pages 226-237
New Results on the Complexity of the Max- and Min-Rep Problems....Pages 238-247
In-Place Sorting....Pages 248-259
On d -Regular Schematization of Embedded Paths....Pages 260-271
Upward Point-Set Embeddability....Pages 272-283
Cooperative Query Answering by Abstract Interpretation....Pages 284-296
An Improved B+ Tree for Flash File Systems....Pages 297-307
Comparing GPU and CPU in OLAP Cubes Creation....Pages 308-319
A Power Consumption Analysis Technique Using UML-Based Design Models in Embedded Software Development....Pages 320-331
Advice Complexity and Barely Random Algorithms....Pages 332-343
Alternative Parameterizations for Cluster Editing....Pages 344-355
The Complexity of Finding k th Most Probable Explanations in Probabilistic Networks....Pages 356-367
Optimal File-Distribution in Heterogeneous and Asymmetric Storage Networks....Pages 368-381
On the Complexity of the Metric TSP under Stability Considerations....Pages 382-393
Structural Properties of Hard Metric TSP Inputs....Pages 394-405
An Automata-Theoretical Characterization of Context-Free Trace Languages....Pages 406-417
Unambiguous UML Composite Structures: The OMEGA2 Experience....Pages 418-430
Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages....Pages 431-443
A Local Search Algorithm for Branchwidth....Pages 444-454
Finding the Description of Structure by Counting Method: A Case Study....Pages 455-466
On Approximating the d -Girth of a Graph....Pages 467-481
SScAC: Towards a Framework for Small-Scale Software Architectures Comparison....Pages 482-493
Folk Theorems on the Correspondence between State-Based and Event-Based Systems....Pages 494-505
Privacy, Liveliness and Fairness for Reputation....Pages 506-519
Minimizing Interference for the Highway Model in Wireless Ad-Hoc and Sensor Networks....Pages 520-532
Join-Queries between Two Spatial Datasets Indexed by a Single R*-Tree....Pages 533-544
Information Leakage Analysis by Abstract Interpretation....Pages 545-557
Partition into Triangles on Bounded Degree Graphs....Pages 558-569
Back Matter....Pages -