Fun with Algorithms

Name: Fun with Algorithms | 6th International Conference, FUN 2012, Venice, Italy, June 4-6, 2012, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

6th International Conference, FUN 2012, Venice, Italy, June 4-6, 2012, Proceedings

Evangelos Kranakis DANNY KRIZANC Flaminia Luccio(Herausgeber*in)

Springer (Verlag)

1. Auflage

Erschienen am 31. Mai 2012

XI, 397 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-30347-0 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken