WALCOM: Algorithms and Computation

Name: WALCOM: Algorithms and Computation | 10th International Workshop, WALCOM 2016, Kathmandu, Nepal, March 29-31, 2016, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

10th International Workshop, WALCOM 2016, Kathmandu, Nepal, March 29-31, 2016, Proceedings

Mohammad Kaykobad Rossella Petreschi(Herausgeber*in)

Springer (Verlag)

Erschienen am 8. März 2016

XIX, 362 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-319-30139-6 (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

Intro
Preface
Organization
Invited Talks (Abstracts)
Popping Superbubbles and Discovering Clumps: Recent Developments in Biological Sequence Analysis
2-Edge and 2-Vertex Connectivity Problems in Directed Graphs
Social Pressure can Subvert Majority in Social Networks
Beyond Cyber-Physical Era: What's Next?
Contents
Invited Talk
Popping Superbubbles and Discovering Clumps: Recent Developments in Biological Sequence Analysis
1 Introduction
2 Superbubbles
2.1 Biological Motivation
2.2 Definitions
2.3 Properties of Superbubbles
2.4 Algorithms
2.5 Discussion
3 Clumps
3.1 Biological Motivation
3.2 Definitions
3.3 Algorithms
3.4 Discussion
4 Conclusion
References
Graphs Coloring
Tropical Dominating Sets in Vertex-Coloured Graphs
1 Introduction
2 Approximability and Fixed Parameter Tractability
References
On Hamiltonian Colorings of Block Graphs
1 Introduction
2 A Lower Bound for Hamiltonian Chromatic Number of Block Graphs
3 Hamiltonian Chromatic Number of Symmetric Block Graphs
References
Vertex-Coloring with Star-Defects
1 Introduction
2 Coloring Outerplanar Graphs and Subclasses
3 NP-completeness for (Planar) Graphs of Bounded Degree
4 Conclusions
References
Graphs Exploration
Lower Bounds for Graph Exploration Using Local Policies
1 Introduction
2 Worst-Case Behavior of LRV-e and LRV-v
3 Worst-Case Behavior of LFV-v and LFV-e
4 A Graph with Superpolynomial Exploration Time
5 Conclusions
References
Optimal Distributed Searching in the Plane with and Without Uncertainty
1 Introduction
2 Parallel Searching
3 Search Strategy
3.1 Even-Work Strategy for Parallel Search with k=4r Robots
3.2 Parallel Search with Any Number of Robots
4 From Theory to Practice
4.1 The Search Strategy
4.2 Probability of Detection
5 Conclusion
References
Formation of General Position by Asynchronous Mobile Robots Under One-Axis Agreement
1 Introduction
1.1 Earlier Works
1.2 Our Contribution
2 Model and Definitions
3 Algorithm for Making of General Position
3.1 Eligible Robots for Movements
3.2 Computing Destination Point
3.3 Correctness
4 Conclusion
References
Graphs Algorithms
On Aligned Bar 1-Visibility Graphs
1 Introduction
2 Preliminaries
3 Maximality
4 Path-Addition
5 Recognition of Optimal AB1VGraphs
6 Relationship to Other Classes of Graphs
7 Conclusion
References
A Necessary Condition and a Sufficient Condition for Pairwise Compatibility Graphs
1 Introduction
2 Preliminaries
3 Necessary Condition
4 Sufficient Condition
5 Conclusion
References
Mixing Times of Markov Chains of 2-Orientations
1 Introduction
2 Preliminaries
2.1 The Up-Down Markov Chain of -orientations
2.2 2-Orientations and Separating Decompositions
2.3 Markov Chains and Mixing Times
3 Markov Chains for 2-Orientations
3.1 Slow Mixing for 2-Orientations
3.2 The Tower Chain for Low Degree Quadrangulations
3.3 Comparison of M2T and M2
4 Concluding Remarks and Open Problems
References
Computational Geometry
Computing a Minimum-Width Square Annulus in Arbitrary Orientation
1 Introduction
2 Preliminaries
3 Square Annuli in Fixed Orientation
4 Square Annuli over Arbitrary Orientations
4.1 The Invariants
4.2 Combinatorial Changes of the Invariants and Events
4.3 Computing Events
4.4 The Main Loop: Handling the Next Event
4.5 Finding an Optimal Orientation over a Primary Interval
References
A General Framework for Searching on a Line
1 Introduction
2 Searching on a Line with Turn Cost
3 Searching a Moving Target on a Line with Turn Cost
3.1 Turn Cost Is Time --- Competitive with Respect to D
3.2 Turn Cost Is Fuel | Competitive with Respect to D
4 The General Framework
4.1 One More Application of the General Framework
References
An Optimal Algorithm for Computing the Integer Closure of UTVPI Constraints
1 Introduction
2 Statement of Problem
2.1 Constraint Network Presentation
3 Motivation and Related Work
4 A Fast Integer Closure Algorithm for a Special Subclass of UTVPI Constraints
5 The New Algorithm
5.1 Analysis of Running Time
6 Correctness
7 Conclusion
References
Covering Points with Convex Sets of Minimum Size
1 Introduction
2 Preliminary
3 Area-Optimal Covering with Two Convex Hulls
4 Perimeter-Optimal Covering with Two Convex Hulls
5 Extensions
References
Data Structures
Efficient Generation of Top-k Procurements in a Multi-item Auction
1 Introduction
2 Method I: Reduction to k Shortest Paths Problem
3 The Metadata Structure Mlocal
3.1 Metadata Structure Per Partition
3.2 Metadata Structure Per Item
4 Method II: Using Mlocal to Find Top-k Procurements
4.1 The Basic Problem
4.2 Other Variants
5 Conclusions and Future Research
References
Counting Subgraphs in Relational Event Graphs
1 Introduction
2 Preliminaries
3 Counting Quadrangles
4 Counting Triangles and Other Subgraphs
4.1 Counting Triangles
4.2 Counting Complete and Maximal Complete Subgraphs
5 Conclusion
References
Computational Complexity
Large Independent Sets in Subquartic Planar Graphs
1 Introduction
2 Preliminaries
3 Fixed-Parameter Algorithm in Subquartic Planar Graphs
4 Discussion
References
As Close as It Gets
1 Introduction
2 Preliminaries
3 Results
4 Duality and Inapplicability of Clone Closure
5 Finding the Minimal Distance Between Solutions
5.1 Polynomial-Time Cases
5.2 Hard Cases
6 Concluding Remarks
References
Shortest Reconfiguration of Sliding Tokens on a Caterpillar
1 Introduction
2 Preliminaries
3 Proper Interval Graphs
4 Caterpillars
5 Concluding Remarks
References
Approximation Algorithms
Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers
1 Introduction
1.1 Previous Work and Ours
2 Preliminaries
3 A Local Algorithm for EDS, M2-EDS, and 2-TVC
4 A Local Algorithm for S2-EDS and 3-TVC
References
Approximation Algorithms for Generalized Bounded Tree Cover
1 Introduction
2 Tree Cover for Graphs with Multiple Weight Functions
2.1 Strong Tree Cover
2.2 Weak Tree Cover
3 Tree Cover with Different Bounds
4 Conclusion
References
Approximation Algorithms for Three Dimensional Protein Folding
1 Introduction
2 Preliminaries
3 Our Approaches
3.1 Upper Bound
3.2 Approximation Algorithms and Lower Bounds
4 Conclusion
References
Parameterization of Strategy-Proof Mechanisms in the Obnoxious Facility Game
1 Introduction
1.1 Social Choice Theory
1.2 Facility Game
1.3 Our Contribution
2 Preliminaries
2.1 Notation
2.2 Strategy Proofness
2.3 Masking Zone Mechanisms
2.4 Social Benefit
2.5 Obnoxious Facility Game in the Line Metric
3 Masking Zone Mechanisms
4 Upper Bounds on the Benefit Ratio
5 Lower Bounds on the Benefit Ratio
6 Concluding Remarks
References
On-line Algorithms
Optimal Online Algorithms for the Multi-objective Time Series Search Problem
1 Introduction
1.1 Previous Work
1.2 Our Contribution
2 Preliminaries
2.1 Multi-Objective Online Problems
2.2 Competitive Analysis for Multi-Objective Online Problems
2.3 Multi-objective Time Series Search Problem
3 Observations on the Competitive Analysis
4 Online Algorithm: Balanced Price Policy
4.1 The Algorithm BPPk is Best Possible
4.2 Discussions
5 Analysis for Competitive Ratio
5.1 Worst Component Competitive Ratio
5.2 Arithmetic Mean Component Competitive Ratio
5.3 Geometric Mean Component Competitive Ratio
References
Fully Dynamically Maintaining Minimal Integral Separator for Threshold and Difference Graphs
1 Introduction
2 Preliminaries
3 A Data Structure for Computing Minimal Integral Separator for Threshold or Difference Graphs
4 Adding/deleting an Edge to Threshold/difference Graphs
5 Adding/deleting a Node to Threshold/difference Graphs
6 Disjoint Union and Join of Two Threshold Graphs
References
Algorithms
A Lagrangian Relaxation-Based Heuristic to Solve Large Extended Graph Partitioning Problems
1 Introduction
2 Quadratic Programming Formulation
3 Lagrangian Relaxation
4 Lagrangian Heuristic
5 Genetic Algorithm Based Matheuristic
6 Computational Results
7 Conclusions
References
Semimetric Properties of Sørensen-Dice and Tversky Indexes
1 Introduction
1.1 Our Contribution
2 Robust Jaccard Index
2.1 Relation with Other Indexes
3 Metric Properties
4 Conclusions and Future Work
References
Finding Mode Using Equality Comparisons
1 Introduction
1.1 Related Work
2 Finding Mode Using O(n2m) Comparisons
3 Finding Mode in O(n2m) Time
3.1 A Simple Mode Finding Algorithm
3.2 An Improved Algorithm -- Generalization of the Fischer-Salzberg Majority Algorithm
4 Finding the Mode When m is Not Known
5 Conclusions
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken