WALCOM: Algorithms and Computation

Name: WALCOM: Algorithms and Computation | 12th International Conference, WALCOM 2018, Dhaka, Bangladesh, March 3-5, 2018, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

12th International Conference, WALCOM 2018, Dhaka, Bangladesh, March 3-5, 2018, Proceedings

M. Sohel Rahman Wing-Kin Sung Ryuhei Uehara(Herausgeber*in)

Springer (Verlag)

Erschienen am 21. Februar 2018

XX, 265 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-319-75172-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
Optimal Sink Location Problems on Dynamic Flow Networks
Logic in Computational Biology
Morphing Planar Graph Drawings
Contents
A Simple Algorithm for r-gatherings on the Line
1 Introduction
2 r-gather-clustering on the Line
3 r-gathering
4 Conclusion
References
Enumeration of Nonisomorphic Interval Graphs and Nonisomorphic Permutation Graphs
1 Introduction
2 Preliminaries
3 General Framework
4 Enumeration of Nonisomorphic Interval Graphs
4.1 Canonical Representation
4.2 Parent-Child Relationship
4.3 Algorithm Analysis
4.4 Three Variants of Enumeration
5 Enumeration of Nonisomorphic Permutation Graphs
5.1 Canonical Representation
5.2 Parent-Child Relationship
5.3 Algorithm Analysis
6 Experimental Results
7 Concluding Remarks
References
Secret Key Amplification from Uniformly Leaked Key Exchange Complete Graph
1 Introduction
2 Known Results
3 Simple Protocol for up to 2n-3 Keys
4 Finding the Minimum Leak Probability
4.1 Formula for
4.2 Examples of Polynomials
5 Comparison
6 Conclusion
References
Approximating Partially Bounded Degree Deletion on Directed Graphs
1 Introduction
1.1 Our Work and Contributions
1.2 Notations and Definitions
2 Approximating PBDD via Submodular Optimization
3 Fully Bounded Degree Deletion
4 Partially Bounded Degree Deletion
4.1 Approximation Hardness
4.2 Approximation Algorithm
References
Minimum-Width Annulus with Outliers: Circular, Square, and Rectangular Cases
1 Introduction
2 Preliminaries
3 Circular Annulus with Outliers
4 Square Annulus with Outliers
4.1 Configuration of Optimal Solutions
4.2 Finding Candidate Outer Squares
4.3 Finding the Largest Inner Square for a Candidate Pair
5 Rectangular Annulus with Outliers
5.1 Finding the Smallest-Width Annulus for a Fixed Outer Rectangle
5.2 Putting it all Together
References
Minimum-Width Square Annulus Intersecting Polygons
1 Introduction
2 Preliminaries
3 Minimum-Width Square Annulus for Polygons
3.1 Computing Voronoi Diagrams
3.2 Searching the Region Between Two Polygonal Terrains
4 Minimum-Width Square Annulus for Convex Polygons
4.1 Properties of the Farthest-Outer Voronoi Diagram
4.2 Computing the Farthest-Outer Voronoi Diagram
4.3 Searching the Region Between Two Polygonal Terrains
References
Two New Schemes in the Bitprobe Model
1 Introduction
1.1 The Problem Statements
1.2 Previous Results
1.3 Our Contribution
2 Arrangement of Elements
3 The Adaptive Scheme
3.1 Our Datastructure
3.2 The Query Scheme
3.3 The Storage Scheme
4 The Non-adaptive Scheme
4.1 Our Datastructure
4.2 The Query Scheme
4.3 The Storage Scheme
5 Conclusion
References
Faster Network Algorithms Based on Graph Decomposition
1 Introduction
1.1 Related Work
1.2 Our Contribution
2 Preliminaries
2.1 BC-Trees
2.2 SPQR Trees
2.3 Mimicking Networks
2.4 Tree Product Queries
3 Preprocessing
3.1 Constructing D0 Data Structure
3.2 Constructing D1 Data Structure
3.3 Constructing D2 Data Structure
4 Computing s-t Max Flow in O(m+nr) Time
5 Algorithms for MFIP
5.1 Algorithms for Fast Queries
5.2 An Algorithm with Small Index
6 Dynamic Update and Query
7 Algorithms for Other Problems
8 Concluding Remarks
References
An Improvement of the Algorithm of Hertli for the Unique 3SAT Problem
1 Introduction
2 Hertli's Algorithm
3 Our Improvements
References
Random Popular Matchings with Incomplete Preference Lists
1 Introduction
1.1 Popular Matching
1.2 Related Work
1.3 Our Results
2 Preliminaries
3 Complete Preference Lists Setting
4 Incomplete Preference Lists Setting
4.1 Top-Choice Graph
4.2 Size of A2
5 Main Results
5.1 Upper Bound
5.2 Lower Bound
5.3 Phase Transition
5.4 Discussion
References
Scheduling Batch Processing in Flexible Flowshop with Job Dependent Buffer Requirements: Lagrangian Relaxation Approach
1 Introduction
2 Notation and Integer Programming Formulation
2.1 Integer Programming Formulation
3 Lagrangian Relaxation
3.1 Solution of the Lagrangian Relaxation Subproblems
3.2 Choice of the Planning Horizon
4 Lagrangian Heuristic
4.1 Wait Algorithm
5 Computational Experiments
6 Conclusion
References
Computing Periods.
1 Introduction
1.1 Real Computation
1.2 Periods and Their Computational Complexity
2 Our Algorithms and Their Analyses
2.1 Recap on Real Algebraic Geometry
2.2 A Real Randomized Algorithm
2.3 A Deterministic Algorithm
2.4 A Transcendental Algorithm
3 Implementation and Evaluation
3.1 Computing Environment
3.2 Performance Results
3.3 Interpretation
4 Conclusion and Perspectives
References
A Note on Online Colouring Problems in Overlap Graphs and Their Complements
1 Introduction
2 Preliminaries
3 Partitioning an Overlap Graph into Permutation Graphs
4 Competitiveness Through Partitioning
5 Approximation of Offline Variants
6 Concluding Remarks
References
Online Facility Assignment
1 Introduction
1.1 Related Work
1.2 Our Contributions
2 Preliminaries
3 Facility Assignment on a Line
3.1 Algorithm Greedy
3.2 Algorithm -Randomized-Greedy
3.3 Competitive Analysis of Algorithm Optimal-Fill
4 Facility Assignment on Connected Unweighted Graphs
4.1 Competitive Analysis of Algorithm Greedy
4.2 Competitive Analysis of Algorithm Optimal-Fill
5 Facility Assignment with a Finite Service Time
6 Conclusion
References
Fault-Tolerant Complete Visibility for Asynchronous Robots with Lights Under One-Axis Agreement
1 Introduction
2 Model and Preliminaries
3 Algorithm
4 Discussion and Concluding Remarks
References
A Simple, Fast, Filter-Based Algorithm for Circular Sequence Comparison
1 Introduction
1.1 Applications and Motivations
1.2 Our Contribution
1.3 Road Map
2 Preliminaries
3 Brief Literature Review
4 Filtering Algorithm
4.1 Overview of Our Approach
4.2 Filters of SimpLiFiCPM
4.3 The Approach of Our Algorithm
5 Experimental Results
5.1 Datasets
5.2 Environment
5.3 Experimental Results
6 Conclusions
References
Boosting over Non-deterministic ZDDs
1 Introduction
2 Problem Statement and AdaBoost*
2.1 1-Norm Hard Margin Maximization
2.2 AdaBoost*
2.3 AdaBoost
3 A Dag Representation for Samples
3.1 Non-deterministic ZDD (NZDD)
3.2 NZDD Representation for the Sample
3.3 Relations to ZDDs and NFAs
3.4 Complexity of Constructing NZDDs
4 Simulating AdaBoost* over an NZDD Representation for The sample
4.1 Updating the Path Distributions dt
4.2 Computing the Edges t,j
5 Conclusions
References
On Multiple Longest Common Subsequence and Common Motifs with Gaps (Extended Abstract)
1 Introduction
2 Background
2.1 Common Motifs with Gaps
2.2 Multiple Longest Common Subsequence
3 Complexity of Common Motifs with Gaps
4 Algorithms
4.1 A Branch and Bound Algorithm for MLCS Problem
4.2 A Branch and Bound Algorithm for CMG
5 Conclusions
References
FPT Algorithms Exploiting Carving Decomposition for Eulerian Orientations and Ice-Type Models
1 Introduction
2 Definitions
2.1 Graph Definitions
2.2 Carving Decomposition
3 Algorithm for Eulerian Orientations
3.1 Description of Algorithm1
3.2 Correctness and Complexity
4 Algorithm for Ice-Type Models
4.1 Description of Algorithm2
4.2 Correctness and Complexity
5 Conclusion
References
On Structural Parameterizations of Happy Coloring, Empire Coloring and Boxicity
1 Introduction
2 Preliminaries
3 Happy Coloring
4 Empire Coloring
5 Boxicity
References
Complexity of the Maximum k-Path Vertex Cover Problem
1 Introduction
2 Preliminaries
3 NP-Hardness of MaxP3VC on Split Graphs and MaxP4VC on Chordal Graphs
4 Algorithm for MaxP3VC on Trees
5 Algorithm for MaxP3VC on Graphs with Bounded Treewidth
References
On the Parallel Parameterized Complexity of the Graph Isomorphism Problem
1 Introduction
2 Preliminaries
3 GI for Distance to a Graph Class is in Para-AC1
4 GI Parameterized by Vertex Cover is in Para-TC 0
5 Logspace GI Algorithms for Bounded Distance to Graph Classes
6 Conclusion
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken