Fun with Algorithms
6th International Conference, FUN 2012, Venice, Italy, June 4-6, 2012, Proceedings
Published on 31. May 2012
XI, 397 pages
978-3-642-30347-0 (ISBN)
Description
This book constitutes the refereed proceedings of the 6th International Conference, FUN 2012, held in June 2012 in Venice, Italy. The 34 revised full papers were carefully reviewed and selected from 56 submissions. They feature a large variety of topics in the field of the use, design, and analysis of algorithms and data structures, focusing on results that provide amusing, witty but nonetheless original and scientifically profound contributions to the area.
More details
Other editions
Additional editions
Evangelos Kranakis | DANNY KRIZANC | Flaminia Luccio
Fun with Algorithms
6th International Conference, FUN 2012, Venice, Italy, June 4-6, 2012, Proceedings
Book
05/2012
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Organization
- Table of Contents
- Distributed Algorithms by Forgetful Mobile Robots
- References
- Stability and Metastability of the Logit Dynamics of Strategic Games
- References
- Art Galleries, k-modems, and k-convexity
- References
- The Vulcan Game of Kal-Toh: Finding or Making Triconnected Planar Subgraphs
- Introduction
- Recognizing a Winning Graph
- Creating Larger Graphs
- Creating Prisms
- Creating Triconnected Planar Subgraphs of Connected Graphs
- Conclusions
- References
- Scandinavian Thins on Top of Cake: On the Smallest One-Size-Fits-All Box
- Introduction
- The Basic Algorithm
- A Simpler Algorithm
- Rectangular Items
- APTAS
- Convex Suitcase
- References
- The Kissing Problem: How to End a Gathering When Everyone Kisses Everyone Else Goodbye
- Introduction
- The Kissing Problem in a Crowded Room
- The Kissing Problem in a Comfortable Room
- The Kissing Problem in the Sparse Room
- Conclusion
- References
- Mad at Edge Crossings? Break the Edges!
- Introduction
- Basics and the Formal Concept
- Graphs without Fixed Embedding
- How to DrawKn
- A Sufficient Condition for SHPED's with Factor d and a Graph Class with Large SHPED Factor
- Graphs with Fixed Geometric Embedding
- Computation of PEDs of Different Types
- Nearly Complete and Maximal PEDs
- Conclusion and Future Work
- References
- Train Marshalling Is Fixed Parameter Tractable
- Introduction
- Preliminaries
- An FPT Algorithm for k-TM
- Conclusions
- References
- Conflict-Free Graph Orientations with Parity Constraints
- Introduction
- NP-Completeness for Exact and Subset Conflicts
- NP-Completeness of pco-2ec
- NP-Completeness of pco-2sc
- Polynomial Time Algorithms
- Even Orientations with Disjoint Exact Conflict Pairs
- Even Orientations with Disjoint Exact Conflicts
- Even Orientations with Disjoint Subset Conflicts
- Conclusion
- References
- The Multi-interval Ulam-R´enyi Game
- Prologue
- Introduction
- BasicFacts
- Query Optimal Multi-interval Search with k = O(e2)
- Epilogue: Towards a Canonical Representation of States and Multi-interval Queries
- References
- Picture-Hanging Puzzles
- Introduction
- Puzzles
- Basic Theory: 1-out-of-n
- Connection to Borromean and Brunnian Links
- Connection to Free Group
- 1-out-of-n
- Disjoint Subsets of Nails
- General Theory
- Connection to Monotone Boolean Functions
- Arbitrary Monotone Boolean Functions
- Worst-Case Optimality
- Spectating Is Hard
- OpenProblems
- References
- Optimal Sensor Networks for Area Monitoring Using Rotating and Beam Sensors
- Introduction
- Preliminaries
- Our Results
- Monitoring the Plane Using Rotating and Beam Sensors
- Monitoring the Plane Using Rotating Sensors Only
- Monitoring a Finite Area
- Conclusions
- References
- The Byzantine Brides Problem
- Introduction
- Model and Definitions
- State Model
- Self-stabilizing Protocols Resilient to Byzantine Faults
- Specification
- Strictly Stabilizing Maximal Marriage
- Our Protocol
- Proof of Strict Stabilization
- Optimality of Containment Radius
- Related Works
- Conclusion
- References
- Lean Programs, Branch Mispredictions, and Sorting
- Introduction
- Appetizer: Heap Construction
- General Program Transformation
- Heapsort
- Mergesort
- Conclusion
- References
- On Computer Integrated Rationalized Crossword Puzzle Manufacturing
- Introduction
- Crossword Puzzle Mask Generation-Step One
- Filling a Crossword Puzzle Mask-Step Two
- References
- Solving Single-Digit Sudoku Subproblems
- Introduction
- Nishio
- Algorithm
- Analysis
- Implementation
- Hardness
- Conclusions
- References
- Finding Good Coffee in Paris
- Introduction
- Modelling the Paris M´etro
- Finding the Good Coffee
- Proving It Works on Every Subway-Like Network
- References
- To Satisfy Impatient Web Surfers Is Hard
- Introduction
- Preliminaries
- The Surveillance Game
- Restriction to Induced Paths
- Difficult Problems
- Polynomial-Time Algorithms in Some Graph Classes
- Keeping Tree under Surveillance
- To Keep an Interval Graph under Surveillance
- Conclusion and Further Work
- References
- Making Life Easier for Firefighters
- Introduction
- Preliminaries
- Pk-Free Graphs
- Interval Graphs
- Permutation Graphs
- Concluding Discussion and Unit Disk Graphs
- References
- Counting Perfect Matchings in Graphs of Degree 3
- Introduction
- The Trivial Operations and Extensions to the Weighted Case
- Usingthem - n Measure
- Improved Bound for Degree 3 Graphs
- The Running Time of the Faster Matching Count Algorithm
- References
- M.C. Escher Wrap Artist: Aesthetic Coloring of Ribbon Patterns
- Introduction
- Escher Tiles
- Ribbon Patterns
- Natural Periods and the Period Lattice
- MainResult
- Open Questions
- References
- On the Complexity of Rolling Block and Alice Mazes
- Introduction
- Definitions
- Rolling Block Mazes
- Rolling Block Mazes with an Unbounded Number of Blocks
- Rolling Block Mazes with a Bounded Number of Blocks
- Alice Mazes
- Alice Mazes with an Unbounded Number of Tokens
- Alice Mazes with a Bounded Number of Tokens
- Conclusions
- References
- Grid Graphs with Diagonal Edges and the Complexity of Xmas Mazes
- Introduction
- Definitions
- Undirected Grid Graph Reachability, Revisited
- Xmas (Tree) Mazes
- Xmas Mazes with a Bounded Number of Sticks
- Xmas Mazes with an Unbounded Number of Sticks
- Conclusions
- References
- Algorithms and Complexity of Generalized River Crossing Problems
- Introduction
- River Crossing Problems
- Definitions
- Related Work
- Minimizing the Number of Transportations
- NP-Hardness for Any Fixed b = 3
- Polynomially Solvable Problems with FL = FR = Ø and b = 2
- Determining Reachability Only
- Summary
- References
- Solving Tantrix via Integer Programming
- Introduction
- Tantrix
- A Problem Setting and Terminology for Formulations
- A Problem Setting for Solving Tantrix by a Computer
- Terminology and Definitions for IP Formulations
- An Integer Programming Formulation
- Variables
- Constraints and an Objective Function
- Elementary Experiments and the Results
- Improvement of Formulations for Valid Tantrix Solutions
- Arranging Solution Shapes to Be Round and Holeless
- Eliminate Short Subloops in Advance
- Further Challenge
- Conclusion
- References
- Scrabble Is PSPACE-Complete
- Introduction
- Our Model of Scrabble - Definitions
- Hardness Due to Placement of the Words
- Hardness Due to Formation of the Words
- Construction Sketch
- The Initial Position
- Assignment Phase
- Satisfaction Phase
- Constant Rack and Word Size
- Conclusions
- References
- Practical Algorithms for Generating a Random Ordering of the Elements of a Weighted Set
- Introduction
- Statement of Problem
- Sources of Randomness
- Information-Theoretic Lower Bounds
- Existing Algorithms
- O(n2) Algorithm Based on the Alias Method for Sampling
- O(n ·U) Algorithm Obtained by Generalizing the Knuth Shuffle
- O(n log n) Algorithm Based on Wong-Easton Sampling
- O(n) Theoretical Algorithm Based on Matias-Vitter-Ni Sampling
- New Practical Algorithms
- Building Block: Random Riffle Merge
- O(n log n) Algorithm Based on Random Riffle Merge
- Practical Algorithms That Can Beat O(n log n)
- O(n log logU) Cost for Worst-Case Inputs
- O(n log log n) Cost for Worst-Case Inputs
- O(n) Expected Cost for Realistic Non-Worst-Case Weight Distributions
- Experiments
- References
- Spanning Trees and the Complexity of Flood-Filling Games
- Introduction
- Notation and Definitions
- Spanning Trees
- Graphs with Polynomial Bounds on the Numbers of Connected Subgraphs
- The FREE-FLOOD-IT Case
- The Complexity of k-LINKING FLOOD IT
- Conclusions and Open Problems
- References
- Tron, a Combinatorial Game on Abstract Graphs
- Introduction
- Basic Observations
- Extremal Question
- Complexity Question
- References
- Divorcing Made Easy
- Introduction
- Formal Definition of the Allocation Problem
- Combinatorial Characterizations
- An Efficient Algorithmic Characterization
- A Simple Allocation Rule for Divorce Situations
- References
- A New Analysis of Best Fit Bin Packing
- Introduction
- TheClassof GoodFit Algorithms
- Seniors, Juniors and Their Credits
- References
- The Coolest Order of Binary Strings
- Famous Orders of Binary Strings
- Fixed-Weight Binary Strings
- New Results
- The Coolest Order of Binary Strings
- The Coolest Successor Rule
- Coool and Cooool Parity Restrictions
- A Family of de Bruijn Sequences
- The Grand-Daddy de Bruijn Sequence
- The Cool-Daddy de Bruijn Sequence
- La Pecora Nera de Bruijn Sequence
- The Coolest de Bruijn Sequences
- References
- Hitori Number
- Introduction
- Definitions
- OurResults
- Lower Bound
- Upper Bound
- Conclusions
- References
- Computing Maximum Hamiltonian Paths in Complete Graphs with Tree Metric
- Introduction
- Alternating Sequences and Maximum Hamiltonian Paths
- Some Useful Combinatorics of Alternating Sequences
- Centroids in Trees
- Computing Maximum Hamiltonian Paths
- FinalRemarks
- References
- Gaming Is a Hard Job, But Someone Has to Do It!
- Introduction
- Metatheorems
- Location Traversal and Single-Use Paths
- Doors and Pressure Plates
- Doors and Switches
- Applications and Further Results
- References
- Hardness of Mastermind
- Introduction
- Definitions
- Counting Mastermind Solutions
- Related Results
- FurtherResearch
- References
- Scienceography: The Study of How Science IsWritten
- Introduction
- Data Collection
- Structure Analysis
- Comments
- Length
- Package Use
- Number of Authors
- Theorems
- Comparison between Math and CS
- Concluding Discussions
- References
- Author Index
