[Lecture Notes in Computer Science] WALCOM: Algorithms and Computation Volume 12049 (14th International Conference, WALCOM 2020, Singapore, Singapore, March 31 – April 2, 2020, Proceedings) ||

This book constitutes the refereed proceedings of the 14th International Conference on Algorithms and Computation, WALCOM 2020, held in Singapore in March/April 2020. The 23 full and 4 short papers presented were carefully reviewed and selected from 66 submissions. The papers focus on algorithmic graph theory and combinatorics, computational biology, computational geometry, data structures, experimental algorithm methodologies, graph algorithms, graph drawing, parallel and distributed algorithms, network optimization. Preface Organization Contents Invited Talks Drawing Planar Graphs 1 Introduction 2 Reduction to Planarity Testing 3 Incremental Modification 4 SPQR-Tree Decomposition 5 Conclusions References Space Efficient Separator Algorithms for Planar Graphs 1 Summary 2 Preliminaries for Our Discussion References Recent Progresses in the Combinatorial and Algorithmic Study of Rooted Phylogenetic Networks 1 Basic Definitions 2 Component Graphs 3 Network Classes and Inclusion Relations 4 Generating and Counting Tree-Child Networks 5 The Cluster and Tree Containment Problems References Long Papers Optimum Algorithm for the Mutual Visibility Problem 1 Introduction 1.1 Earlier Works 1.2 Our Contribution 2 Model and Notations 3 Mutual Visibility Under the FSYNC model 3.1 Algorithm MutualVisibilityFsync() 3.2 Algorithm ComputeDestination() 3.3 Correctness of MutualVisibilityFsync() References Routing in Histograms 1 Introduction 2 Preliminaries 3 Simple Histograms 4 Double Histograms References A Waste-Efficient Algorithm for Single-Droplet Sample Preparation on Microfluidic Chips 1 Introduction 2 Preliminaries 3 Algorithm Description 4 Construction of Converters 4.1 (i:14, J:12)-Converters Ci,j2 5 Performance Bounds 6 Experimental Study 7 Final Comments References Shortest Covers of All Cyclic Shifts of a String 1 Introduction 2 Applications of the Suffix Tree 3 Covers of Cyclic Shifts 4 Main Algorithm 5 Strings with Arbitrarily Large Size of CyCoSet(S) 6 Conclusions and Open Problems References Packing Trees into 1-Planar Graphs 1 Introduction 2 Preliminaries 3 Trees that Do Not Admit 1-Planar Packings 4 1-Planar Packings of Two Paths and a Caterpillar 5 1-Planar Packings with Constant Edge Crossings 6 From Triples to Quadruples 7 Open Problems References Angle Covers: Algorithms and Complexity 1 Introduction 2 Preliminaries and Examples 3 Algorithms for Graphs with Restricted Degrees 4 NP-Hardness for Graphs of Maximum Degree 5 5 Generalizations 6 Isomorphic Thickness 7 Conclusion and Open Problems References Fast Multiple Pattern Cartesian Tree Matching 1 Introduction 2 Problem Definition 2.1 Notation 2.2 Multiple Pattern Cartesian Tree Matching 3 Fingerprinting Methods 3.1 Parent-Distance Encoding 3.2 Binary Encoding 4 Fast Multiple Pattern Cartesian Tree Matching Algorithms 4.1 Algorithm Based on Wu-Manber 4.2 Algorithm Based on Rabin-Karp 4.3 Algorithm Based on Alpha Skip Search 4.4 Selecting the Block Size 5 Experiments 5.1 Evaluation on the Equal Length Patterns 5.2 Evaluation on the Different Length Patterns 5.3 Evaluation on the Real Dataset References Generalized Dictionary Matching Under Substring Consistent Equivalence Relations 1 Introduction 2 Preliminaries 3 SCER Automata 3.1 Definition and Properties 3.2 Dictionary Matching Using SCERA 3.3 Constructing SCERA References Reconfiguring k-path Vertex Covers 1 Introduction 2 Preliminaries 3 Hardness Results 4 Polynomial-Time Algorithms 4.1 Trees 4.2 Paths and Cycles 5 Concluding Remarks References Computational Complexity of the Chromatic Art Gallery Problem for Orthogonal Polygons 1 Introduction 2 Definitions and Results 3 NP-Completeness 3.1 3SAT Problem 3.2 Transformation from an Instance of Clause-Linked Planar 3SAT to an Orthogonal Polygon References Maximum Bipartite Subgraph of Geometric Intersection Graphs 1 Introduction 2 NP-Hardness 3 Algorithmic Results 3.1 Interval Graphs 3.2 Circular-Arc Graphs 4 Approximation Algorithms 4.1 Unit Disks and Unit Squares 4.2 Unit-Height Rectangles 5 NP-Hardness of MTFS 6 Conclusion References The Stub Resolution of 1-Planar Graphs 1 Introduction 2 Preliminaries and Proof Strategy 3 Straight-Line Drawings 4 Polyline Drawings 5 Open Problems References Dispersion of Mobile Robots on Grids 1 Introduction 2 Model Details and Preliminaries 3 Algorithm in the Local Communication Model (Theorem 1) 4 Algorithm in the Global Communication Model (Theorem 2) 5 Concluding Remarks References Packing and Covering with Segments 1 Introduction 1.1 Related Work 1.2 Our Contributions 2 Preliminaries 3 Algorithms: Segments Anchored from One Side 3.1 The Independent Set Problem 3.2 The Piercing Set Problem 4 Independent Set Problem 5 Piercing Set Problem 6 Dominating Set Problem 6.1 Segments Anchored on a Line with Slope -1 6.2 Unit Segments in the Plane References Implicit Enumeration of Topological-Minor-Embeddings and Its Application to Planar Subgraph Enumeration 1 Introduction 2 Preliminaries 2.1 Graphs and Colored Graphs 2.2 Topological Minors and Characterizations of Graphs 2.3 Decision Diagram (DD) 2.4 Colorful Frontier-Based Search (CFBS) 3 Algorithms 3.1 Implicit Enumeration of TM-Embeddings 3.2 Constraints for Forbidden Topological Minors 3.3 Enumerating Subgraphs Having FTM-Characterizations 4 Computational Experiments 4.1 Settings 4.2 Comparing Several Methods to Enumerate Planar Subgraphs 5 Conclusion References Partitioning a Graph into Complementary Subgraphs 1 Introduction 2 Preliminaries 2.1 M Is Empty 3 Comp-Sub() on Subclasses of Chordal Graphs 3.1 Unit Interval Graphs 3.2 Strongly Chordal Graphs 3.3 Starlike, Block, and Split Graphs 4 M Induces a Complete Bipartite Graph References On the Maximum Edge-Pair Embedding Bipartite Matching 1 Introduction 1.1 Our Contribution 2 Problem Definition 3 Inapproximability Results 4 Results for Small k 4.1 Polynomial Time Algorithm for k = 1 4.2 NP-Hardness for k 2 4.3 Approximation Algorithm 5 Conclusion References Packing Arc-Disjoint Cycles in Bipartite Tournaments 1 Introduction 2 Preliminaries 3 An FPT Algorithm Using Color Coding 4 An Erdös-Pósa Type Theorem 5 A Polynomial Kernel 6 An Improved FPT Algorithm 7 Conclusion References Matching Random Colored Points with Rectangles 1 Introduction 2 Preliminaries 3 The Markov Chains 4 The Markov Chain for k=3 5 Discussion and Open Problems References Designing Survivable Networks with Zero-Suppressed Binary Decision Diagrams 1 Introduction 2 Preliminaries 2.1 Notation 2.2 Survivable Network Design Problem 2.3 Zero-Suppressed Binary Decision Diagrams 3 Proposed Method 3.1 ZDD Construction 3.2 Multinomial Disjoint Join 4 Experiments 4.1 Performance of Multinomial Disjoint Join 4.2 Performance of Proposed Method 5 Conclusion References Approximability of the Independent Feedback Vertex Set Problem for Bipartite Graphs 1 Introduction 1.1 Related Results and Known Results 1.2 Our Contribution 2 Preliminaries 3 Inapproximability 3.1 Gadgets 3.2 Reduction 4 Approximation Algorithm 5 Conclusion References Efficient Enumeration of Non-isomorphic Ptolemaic Graphs 1 Introduction 2 Preliminaries 2.1 Tree Structure for a Ptolemaic Graph 3 Enumeration Algorithms 3.1 Enumeration of Minimal CL-trees 3.2 Distribution of Extra Vertices 4 Concluding Remarks References Faster Privacy-Preserving Computation of Edit Distance with Moves 1 Introduction 1.1 Motivation 1.2 Related Work 1.3 Our Contribution 2 Preliminaries 2.1 EDM 2.2 Homomorphic Encryption 3 Two-Party Secure Consistent Labeling 3.1 Hash Function 3.2 Algorithm 4 Experimental Results 5 Conclusion References Short Papers Parameterized Algorithms for the Happy Set Problem 1 Introduction 1.1 Our Problem and Contributions 1.2 Related Work 2 Preliminaries 3 Parameterized Complexity of MaxHS References An Experimental Study of a 1-Planarity Testing and Embedding Algorithm 1 Introduction 2 Algorithm Design and Experiments 3 Open Problems References Trichotomy for the Reconfiguration Problem of Integer Linear Systems 1 Introduction 2 Preliminaries 3 The General Case of Z(I) = 1 4 Tractable Subclass of Z(I) = 1 5 The Cases of Z(I) 1 6 Conclusion References Train Scheduling: Hardness and Algorithms 1 Introduction 1.1 Our Results 1.2 Related Work 2 Preliminaries 3 Hardness of Scheduling Trains 4 Extending Schedules Within Near-Optimal Runtime References Author Index