Algorithms and Discrete Applied Mathematics: 8th International Conference, CALDAM 2022, Puducherry, India, February 10–12, 2022, Proceedings

Description

This book constitutes the proceedings of the 8th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2022, which was held in Puducherry, India, during February 10-12, 2022. The 24 papers presented in this volume were carefully reviewed and selected from 80 submissions. The papers were organized in topical sections named: graph theory, graph algorithms, computational geometry, algorithms and optimization. Preface Organization Abstracts of Invited Talks All-Pairs Shortest Paths and Fine-Grained Complexity Linear Programming and its Uses in Algorithm Design Approximation Algorithms for Some Geometric Optimization Problems Contents Graph Theory A Proof of the Multiplicative 1-2-3 Conjecture 1 Introduction 2 Proof of Theorem 1 References Chromatic Bounds for Some Subclasses of (P3P2)-free graphs 1 Introduction 2 Preliminaries 3 {P3P2, (K1K2)+Kp}-free graphs 4 {P3P2, 2K1+Kp}-free graphs References List Homomorphisms to Separable Signed Graphs 1 Motivation and Background 2 Path-Separable Signed Graphs 3 Cycle-Separable Signed Graphs 4 Conclusions References Some Position Problems for Graphs 1 Introduction 2 The Smallest Graph with Given mp- and gp-Numbers 3 The Largest Size of Graphs with Given Order and Position Numbers 4 The Diameters of Graphs with Given Order and mp-Number References Comparability Graphs Among Cover-Incomparability Graphs 1 Introduction 2 Ptolemaic Graph 3 Cograph and Distance-Hereditary Graph 4 Bisplit Graphs 5 Composition of C-I Graphs References Graph Algorithms Complexity of Paired Domination in AT-free and Planar Graphs 1 Introduction 2 Preliminaries 2.1 Basic Notations and Definitions 2.2 AT-free Graphs 3 Approximation Algorithm 4 Exact Polynomial-Time Algorithm 5 Paired Domination in Planar Graphs 6 Concluding Remarks References The Complexity of Star Colouring in Bounded Degree Graphs and Regular Graphs 1 Introduction 2 Definitions 3 Bounded Degree Graphs 3.1 4-Star Colouring 3.2 5-Star Colouring 4 Regular Graphs 5 Conclusion References On Conflict-Free Spanning Tree: Algorithms and Complexity 1 Introduction 2 Preliminaries 3 Computational Complexity References B0-VPG Representation of AT-free Outerplanar Graphs 1 Introduction 1.1 Literature 1.2 Terminology and Notation 2 Linear Outerplanar Graphs 3 B0-VPG Representation of 2-connected Linear Outerplanar Graphs 4 Concluding Remarks References P Versus NPC: Minimum Steiner Trees in Convex Split Graphs 1 Introduction 2 STREE in Split Graphs with Convexity on I 2.1 Star-Convex Split Graphs 2.2 Comb-Convex Split Graphs 2.3 Path-Convex Split Graphs 3 STREE in Split Graphs with Convexity on K 3.1 Tree-Convex Split Graphs References On cd-Coloring of {P5,K4}-free Chordal Graphs 1 Introduction 2 Preliminaries 3 {P5,K4}-free Chordal Graphs 4 P6-free Chordal Bipartite Graphs 5 Conclusion References An Output-Sensitive Algorithm for All-Pairs Shortest Paths in Directed Acyclic Graphs 1 Introduction 1.1 Paper Organization 2 An Application of DAG SSSP Method to Arbitrary Digraphs 3 An Output-Sensitive APSP Algorithm for DAGs 4 A Potential Extension to Digraphs with Large Cycles 5 Final Remarks References Covering a Graph with Densest Subgraphs 1 Introduction 2 Definitions 2.1 Algorithms for Densest Subgraph 3 A Polynomial Time Algorithm for the k-Densest Cover Subgraphs 4 An Approximation Algorithm for Top k-Cover-Densest Subgraphs 5 Conclusions and Open Problems References Computational Geometry Coresets for (k, )-Median Clustering Under the Fréchet Distance 1 Introduction 1.1 Related Work 1.2 Our Contributions 1.3 Organization 2 Coresets for Generalized k-Median Clustering in Metric Spaces 2.1 Sensitivity Bound 2.2 Coresets by Sensitivity Sampling 3 Coresets for (k,)-Median Clustering Under the Fréchet Distance 4 Towards Practical (1,)-Median Approximation Algorithms 5 Conclusion References Bounds and Algorithms for Geodetic Hulls 1 Introduction 1.1 Related Work 1.2 Contribution 2 Preliminaries 3 Bounds for the Gin of the Graph Contour 4 Bounding the Hull Number 5 Experimental Results 5.1 Graph Hull Sets and Gin 6 Conclusions and Future Work References Voronoi Games Using Geodesics 1 Introduction 1.1 Previous Results 1.2 New Results 2 Preliminaries 2.1 Orthogonal Convex Polygons for the L 1 Metric 2.2 Orthogonal Convex Polyhedra 3 Bounds for Orthogonal Convex Polygons 3.1 Orthogonal Convex Polygon with Clients on Boundary 4 Bounds for Orthogonal Convex Polyhedra 4.1 Orthogonal Convex Polyhedra with Boundary Clients References Algorithms and Optimization Approximation and Parameterized Algorithms for Balanced Connected Partition Problems 1 Introduction 1.1 Our Contribution 2 Approximation Algorithm for Min-Max BCPk 3 Parameterized Algorithm for 1-MAX-MIN BCP 4 Concluding Remarks References Algorithms for Online Car-Sharing Problem 1 Introduction 2 Preliminaries 2.1 Problem Setting and Notations 2.2 -Net-Cost Augmenting Path 3 The Online-Match-and-Assign Algorithm 4 Algorithm Analysis 4.1 Adversarial Order of Arrivals 4.2 Random Order of Arrivals 5 Conclusion References Algebraic Algorithms for Variants of Subset Sum 1 Introduction: Variants of Subset Sum 1.1 Main Results 1.2 Technical Overview 1.3 Prior Works and Their Limitations 2 Preliminaries and Notations 3 Proof of Theorem 1 4 Proof of Theorem 2 5 Conclusion References Hardness and Approximation Results for Some Variants of Stable Marriage Problem 1 Introduction 2 Preliminaries 3 Complete Stable Matching in SMTI-C and SMTI-STEP 3.1 COM SMTI-C Problem 3.2 COM SMTI-STEP Problem 4 Maximum Stable Matching in SMTI-INC Problem 5 Minimum Stable Matching in SMTI-STEP Instance 6 Approximation Algorithm for MIN SMTI-INC 7 Conclusion References On Fair Division with Binary Valuations Respecting Social Networks 1 Introduction 1.1 Related Work 1.2 Our Contributions 2 Preliminaries 3 Envy-Freeness 3.1 NP-Hardness for Two Agent Types 3.2 W-Hardness Parameterized by Goods 3.3 W-Hardness Parameterized by Vertex Cover 3.4 NP-Hardness on Paths 4 Proportionality for Graphs 4.1 Local Proportionality: NP-hardness 4.2 Quasi-Global Proportionality: Efficient Algorithms References Parameterized Intractability of Defensive Alliance Problem 1 Introduction 1.1 Our Main Results 1.2 Known Results 2 Hardness Results of Defensive Alliance 2.1 Proof of Theorem 1 2.2 Proof of Theorem 2 3 Conclusions References On the Approximability of Path and Cycle Problems in Arc-Dependent Networks 1 Introduction 2 Statement of Problems 3 Computational Complexity of SNCC and LoNCC 4 Fixed-Parameter Algorithm for SP 4.1 Intuition 4.2 Randomized Algorithm 4.3 Proof of Correctness 4.4 Derandomization 5 Lower Bound on Kernel Size for the SP Problem 6 Conclusion References Approximation Algorithms in Graphs with Known Broadcast Time of the Base Graph 1 Introduction 2 Exact Algorithm When the Base Graph is a k-Regular mbgs with One Tree 2.1 Broadcast Algorithm When Originator is r 3 Linear Time 1.5-Approximation Algorithm for General Hypercube of Trees 4 Linear Time Constant Approximation Algorithm in Graph of Trees with Known Broadcast Time of the Base Graph 5 Conclusion and Future Work References Author Index