Algorithms and Discrete Applied Mathematics: 9th International Conference, CALDAM 2023, Gandhinagar, India, February 9–11, 2023, Proceedings

Preface
Organization
Abstracts of Invited Talks
	Stable Approximation Schemes
	Graph Modification Problems with Forbidden Minors
	Contents
Algorithms and Optimization
Efficient Reductions and Algorithms for Subset Product
	1 Introduction
		1.1 Our Contributions
		1.2 Prior Works and Limitation of the Obvious Attempts
	2 Preliminaries
	3 Time-Efficient Algorithm for
		3.1 Proof of Theorem 1
	4 An Efficient Reduction from  to
		4.1 Polynomial Time Algorithm for Computing Pseudo-Prime-Factors
	5 Conclusion
	References
Optimal Length Cutting Plane Refutations of Integer Programs
	1 Introduction
	2 Statement of Problems
	3 Motivation and Related Work
	4 Optimal Length Read-Once Refutations
	5 Optimal Length Tree-Like and Dag-Like Refutations
	6 Conclusion
	References
Fault-Tolerant Dispersion of Mobile Robots
	1 Introduction
		1.1 Our Results
	2 Related Work
	3 Model
	4 Crash-Fault Dispersion for Rooted Configuration
		4.1 Algorithm
	5 Crash-Fault Dispersion for Arbitrary Configurations
	6 Conclusion and Future Work
	References
Resource Management in Device-to-Device Communications
	1 Introduction
	2 System Model
	3 Related Work
	4 Branch-n-Cut
		4.1 Cover Cuts
	5 Approximation Algorithm
		5.1 Algorithm
		5.2 Structure
		5.3 Proof of Theorem 1
		5.4 Density Ordered Greedy for KS
	6 Experiments and Results
		6.1 Instance Generation
		6.2 Methodology
		6.3 Results
	7 Conclusion and Future Work
	References
Computational Geometry
Algorithms for k-Dispersion for Points in Convex Position in the Plane
	1 Introduction
		1.1 Literature Survey
	2 Preliminaries
	3 An Exact Fixed-Parameter Algorithm
		3.1 Decision Algorithm
		3.2 The Optimization Scheme
	4 An Exact Polynomial Time Algorithm
	5 Concluding Remarks
	References
Arbitrary-Oriented Color Spanning Region for Line Segments
	1 Introduction
	2 Preliminaries and Notations
		2.1 A Single Color Spanning Strip of Arbitrary Orientation
		2.2 Two Congruent Strips of Arbitrary Orientation
		2.3 Two Congruent Strips of Arbitrary Orientation Whose Union is Color Spanning
		2.4 Color Spanning Rectangle (CSR) of Arbitrary Orientation
	References
Game Theory
Rectilinear Voronoi Games with a Simple Rectilinear Obstacle in Plane
	1 Introduction
	2 Preliminaries
	3 Bounds for Rectilinear Voronoi Games with Polygonal Obstacles
		3.1 Unrestricted
		3.2 Simple Polygon Obstacle
		3.3 Convex Polygon Obstacle
		3.4 Orthogonal Simple Polygon Obstacle
		3.5 Orthogonal Convex Polygon Obstacle
	4 Bounds for Linf Metric in Plane
	References
Diverse Fair Allocations: Complexity and Algorithms
	1 Introduction
	2 Preliminaries
	3 Bounds on the Number of Disjoint and Distinct Allocations
	4 Computing Disjoint and Distinct Allocations
	5 Symmetric Allocations
	6 Conclusion and Future Directions
	7  Appendix
	References
Graph Coloring
New Bounds and Constructions for Neighbor-Locating Colorings of Graphs
	1 Introduction
	2 Gaps Among (G), L(G) and NL(G)
	3 Bounds and Constructions for Sparse Graphs
		3.1 Bounds
		3.2 Tightness
	References
5-List Coloring Toroidal 6-Regular Triangulations in Linear Time
	1 Introduction
		1.1 Motivation
		1.2 Our Work
		1.3 Related Work
	2 Proof of Theorem 1
		2.1 Reductions for the Proof of Case (1)
		2.2 Proof of Case (1)
		2.3 Proofs of Cases (2) to (4)
		2.4 Proof of Non-3-Choosability of the Graphs in Cases (1) to (4)
	References
On Locally Identifying Coloring of Graphs
	1 Introduction
	2 Preliminaries
	3 Graphs with lid(G) = |V(G)|
	4 Block Graphs
	5 Biconvex Bipartite Graphs
	6 Cartesian Product
		6.1 Cartesian Product of a Cycle and a Path
		6.2 Cartesian Product of Two Cycles
	7 Lexicographic Product
	8 Conclusion
	References
On Structural Parameterizations of Star Coloring*-4pt
	1 Introduction
	2 Preliminaries
	3 Neighborhood Diversity
	4 Twin Cover
	5 Clique-Width
	6 Conclusion
	References
Perfectness of G-generalized Join of Graphs
	1 Introduction
	2 When a G-generalized Join of Complete and Totally Disconnected Graphs is Perfect
	3 Perfect Zero-Divisor Graph of a Ring
		3.1 Perfect Ideal Based Zero-Divisor Graph of Rings
		3.2 Zero-Divisor Graph of Rings, Reduced Semigroups and Posets
	References
On Coupon Coloring of Cayley Graphs
	1 Introduction
	2 Preliminaries
	3 Coupon Coloring Number of CAY(R)
	4 Coupon Coloring Number of Rn
	References
Coloring of a Superclass of 2K2-free graphs
	1 Introduction
	2 Preliminaries
	3 {butterfly,hammer}-free graphs
		3.1 {butterfly, hammer, P4+Kp}-free graphs
		3.2 {butterfly, hammer, C4+Kp}-free graphs
		3.3 {butterfly,hammer,(K1K2)+Kp}-free graphs
		3.4 {butterfly,hammer,2K1+Kp}-free graphs
	4 Conclusion
	References
The Weak (2,2)-Labelling Problem for Graphs with Forbidden Induced Structures
	1 Introduction
	2 Preliminaries
	3 Graphs with No Induced Pair of Independent Edges
	4 From 2K2-free Graphs to K1,3-free Graphs, and Beyond
	References
Graph Connectivity
Short Cycles Dictate Dichotomy Status of the Steiner Tree Problem on Bisplit Graphs
	1 Introduction
	2 STREE in Bisplit Graphs
		2.1 Chordal Bisplit Graphs
		2.2 Chordal Bipartite Bisplit Graphs
	3 Complexity of STREE on Bisplit Graphs with Diameter as the Parameter
	4 Parameterized Complexity Results
		4.1 Parameterized Intractability
		4.2 FPT Algorithm for Bisplit Graph
	5 Structural Results on Bisplit Graphs
	References
Some Insights on Dynamic Maintenance of Gomory-Hu Tree in Cactus Graphs and General Graphs
	1 Introduction
		1.1 Related Work and Motivation
	2 Preliminary
	3 Gomory-Hu Trees of Blocks of a Graph
	4 Gomory-Hu Tree of a Cactus Graph
		4.1 Dynamically Maintaining a Gomory-Hu Tree
		4.2 Incremental Algorithm for Gomory-Hu Tree
		4.3 Decremental Algorithm for Gomory-Hu Tree
	5 Gomory-Hu Tree Sensitivity Data Structure
	6 Conclusion and Future Works
	References
Monitoring Edge-Geodetic Sets in Graphs
	1 Introduction
	2 Preliminary Lemmas
	3 Basic Graph Classes and Bounds
		3.1 Trees
		3.2 Cycle Graphs
		3.3 Unicyclic Graphs
		3.4 Complete Graphs
		3.5 Complete Multipartite Graphs
		3.6 Hypercubes
		3.7 Grid Graphs
	4 Relation to Feedback Edge Set Number
	5 Conclusion
	References
Cyclability, Connectivity and Circumference
	1 Introduction
	2 Preliminaries
	3 Proofs of the Results
	4 Concluding Remarks
	References
Graph Domination
On Three Domination-Based Identification Problems in Block Graphs
	1 Introduction
	2 Upper Bounds
		2.1 Identifying Codes
		2.2 Locating-Dominating Codes
		2.3 Open Locating-Dominating Codes
	3 Lower Bounds
	4 Conclusion
	References
Computational Aspects of Double Dominating Sequences in Graphs
	1 Introduction
	2 Preliminaries
	3 NP-Completeness
		3.1 Bipartite Graphs
		3.2 Co-bipartite Graphs
	4 Algorithm for Chain Graphs
	5 Conclusion
	References
Relation Between Broadcast Domination and Multipacking Numbers on Chordal Graphs
	1 Introduction
	2 An Inequality Linking Broadcast Domination and Multipacking Numbers of Chordal Graphs
	3 Unboundedness of the Gap Between Broadcast Domination and Multipacking Numbers of Chordal Graphs
		3.1 Proof of Theorem 4
	4 Conclusion
	References
Cops and Robber on Oriented Graphs with Respect to Push Operation
	1 Introduction
	2 Preliminaries
		2.1 Preliminary Results
	3 Cop-Win Classes Under Strong Push
		3.1 Complete Multipartite Graphs
		3.2 Subcubic Graphs
		3.3 Interval Graphs
	4 Conclusion
	References
Mind the Gap: Edge Facility Location Problems in Theory and Practice
	1 Introduction
		1.1 Contribution
		1.2 Related Work
	2 Edge Center Selection Problems
	3 Hardness and Tractability Results
	4 Approximation Algorithms
		4.1 Parametric Pruning
		4.2 Greedy Selection
	5 Practical Computation
	6 Experiments
		6.1 Results for Small Edge Budgets
		6.2 Results for Large Edge Budgets
	7 Conclusions and Future Work
	References
Complexity Results on Cosecure Domination in Graphs
	1 Introduction
	2 Preliminaries
		2.1 Definitions and Notations
		2.2 Preliminary Results
	3 NP-completeness Result for Split Graphs
	4 Algorithm for Cographs
	5 Approximation Results
		5.1 Upper Bound on Approximation Ratio
		5.2 Lower Bound on Approximation Ratio
		5.3 APX-hardness
	6 Conclusion
	References
Graph Matching
Latin Hexahedra and Related Combinatorial Structures
	1 Intoroduction
	2 Latin Hexahedra
	3 Latin Three-Axis Design and Latin Four-Axis Design
		3.1 1-Factorizations
		3.2 Construction of a Latin Regular Hexahedron Using Latin Three-Axis Designs
	References
Algorithms and Complexity of Strongly Stable Non-crossing Matchings
	1 Introduction
	2 Preliminaries
	3 Strongly Stable Non-crossing Matchings
	4 Semi-strongly Stable Non-crossing Matchings
		4.1 (2,n)-SMI
		4.2 (1,n)-SMI
	5 Conclusion
	A Illustration of Construction of Instance in the Proof of Theorem 2
	References
Minimum Maximal Acyclic Matching in Proper Interval Graphs
	1 Introduction
	2 Algorithm for Proper Interval Graphs
	3 Conclusion
	References
Graph Partition and Graph Covering
Transitivity on Subclasses of Chordal Graphs
	1 Introduction
	2 Notation and Definition
	3 Transitivity in Split Graphs
	4 Transitivity in the Complement of Bipartite Chain Graphs
	5 Nordhaus-Gaddum Type Bounds for Transitivity
	6 Transitively Critical Graphs
	7 Conclusion
	References
Maximum Subgraph Problem for 3-Regular Knödel graphs and its Wirelength
	1 Introduction
	2 Preliminaries
	3 The Knödel graphs
	4 Results
		4.1 Maximum Subgraph Problem
		4.2 Minimum Linear Arrangement
		4.3 Wirelength of Embedding W3,2n, n4 into 1-rooted Complete Binary Tree T1n
	5 Implementation
	6 Concluding Remarks
	References
Graph Covering Using Bounded Size Subgraphs
	1 Introduction
	2 Related Work
	3 Results
		3.1 Constant Factor Approximation Algorithm for BCFC
		3.2 Constant Factor Approximation Algorithm for BSWC
	4 Conclusion and Future Work
	References
Axiomatic Characterization of the Toll Walk Function of Some Graph Classes
	1 Introduction
	2 Preliminaries
		2.1 Transit Functions and Axioms
		2.2 Toll Walks
		2.3 Characterizations by Forbidden Induced Subgraphs
	3 Axioms on the Toll Walk Function
	4 A Characterization of the Toll Walk Function of Subclasses of AT-Free Graphs
	5 A New Characterization of Interval Graphs with a Help of the Toll Walk Function
	References
Structural Parameterization of Alliance Problems
	1 Introduction
		1.1 Previous Work
		1.2 Our Results
	2 FPT Algorithms
		2.1 Alliances Parameterized by Distance to Clique
		2.2 Alliances Parameterized by Twin Cover and the Number of Cliques Outside the Twin Cover
		2.3 Alliances Parameterized by Twin Cover and the Size of the Largest Clique Outside the Twin Cover
	3 Conclusion
	References
Author Index