
WALCOM: Algorithms and Computation
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
The 27 full papers presented together with 4 invited talks were carefully reviewed and selected from 68 submissions. The papers cover a wide range of topics such as approximation algorithms, computational complexity, computational geometry, data structures, graph algorithms, graph coloring, graph exploration, and online algorithms.
More details
Other editions
Additional editions

Content
- 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
System requirements
File format: PDF
Copy protection: Watermark-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Use the free software Adobe Reader, Adobe Digital Editions, or any other PDF viewer of your choice (see eBook Help).
- Tablet/Smartphone (Android; iOS): Install the free app Adobe Digital Editions or another reading app for eBooks, e.g., PocketBook (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (only limited: Kindle).
The file format PDF always displays a book page identically on any hardware. This makes PDF suitable for complex layouts such as those used in textbooks and reference books (images, tables, columns, footnotes). Unfortunately, on the small screens of e-readers or smartphones, PDFs are rather annoying, requiring too much scrolling.
This eBook uses Watermark-DRM, a „soft” copy protection. This means that there are no technical restrictions to prevent illegal distribution. However, there is a personalised watermark embedded in the eBook that can be used to identify the purchaser of the eBook in the event of misuse and to provide evidence for legal purposes.
For more information, see our eBook Help page.