Algorithms and discrete applied mathematics, 6 Conf., CALDAM 2020

Preface......Page 6
Organization......Page 7
Abstracts of Invited Talks......Page 10
Interactions Between Geometry, Graphs and Algorithms......Page 11
The Slow-Coloring Game on a Graph......Page 12
Contents......Page 15
Graph Algorithms......Page 19
 1 Introduction......Page 20
 2 Preliminaries......Page 21
 3 Planar Bipartite Graphs......Page 22
 4 Trees......Page 26
 5 Chordal Graphs......Page 28
 6 Cobipartite Graphs......Page 29
 References......Page 30
 1 Introduction and Motivation......Page 32
 2 The List of Minimal Obstructions......Page 35
 3 The Completeness of the List......Page 37
 5 The Remaining Proofs for Lemma 1......Page 42
 References......Page 43
Monitoring the Edges of a Graph Using Distances......Page 45
 1 Introduction......Page 46
 2 Preliminaries......Page 48
 3 Basic Graph Families and Bounds......Page 49
 4 Complexity......Page 52
 References......Page 56
 1 Introduction......Page 58
 2 Preliminaries......Page 61
 3 Proof of Theorem1......Page 62
 5 The Chain Subgraph Cover Problem......Page 66
 References......Page 68
 1 Introduction......Page 70
 2 Approximations of Modules......Page 71
  2.1 Subset Families......Page 73
 3 -Modules and Basic Properties......Page 74
  3.1 A Symmetric Variation of -Modules......Page 76
  3.2 -Series and -Parallel Operations......Page 77
 4 Computing the Minimal -Modules......Page 79
  5.1 Conclusions and Perspectives......Page 81
 References......Page 82
 2 Releated Work......Page 84
 4 NP-Hardness......Page 86
 5 Approximation Scheme......Page 90
  5.1 Construction of Subsets......Page 92
 References......Page 94
 1 Introduction......Page 96
 2 Non-crossing Hamiltonian Path for Collinear Points......Page 99
  2.1 The Construction......Page 100
  2.2 A Linear Time Algorithm for Non-crossing Hamiltonian Path......Page 101
 3 Minimum Spanning Tree for Collinear Points......Page 103
 4 Minimum Non-crossing Matching for Collinear Points......Page 104
 5 TS Tour for Chunked Points on a Circle......Page 106
 References......Page 108
 1 Introduction......Page 109
 2 Preliminaries......Page 111
  3.1 NP-completeness for Bipartite Graphs......Page 112
  3.2 NP-completeness for Chordal Graphs......Page 113
 4 APX-completeness for Bounded Degree Graphs......Page 115
 5 Conclusion......Page 117
 References......Page 118
 1 Introduction and Results......Page 119
  2.1 NP-hardness on Planar Graphs......Page 121
  2.2 NP-hardness on Line Graphs......Page 123
  2.3 Inapproximability on Graphs with Diameter 2......Page 125
  3.2 Solid Grid Graphs......Page 126
 4 Conclusion......Page 130
 References......Page 131
 1 Introduction......Page 133
 3 NP-completeness......Page 135
 4 Bipartite Permutation Graphs......Page 136
  4.1 Maximal Bicliques......Page 137
  4.2 Our Algorithm......Page 139
 5 Chain Graphs......Page 140
  5.1 Maximal Bicliques......Page 141
  5.2 Our Algorithm......Page 143
 References......Page 144
Graph Theory......Page 146
 1 Introduction......Page 147
 2 Generalized Petersen Graphs......Page 148
 3 Double Generalized Petersen Graphs......Page 152
 References......Page 156
 1 Introduction......Page 157
 2 Self-centeredness of P(n,k) for an Even n......Page 159
 3 Self-centeredness of P(n,k) for Odd n......Page 165
 References......Page 170
 1 Introduction......Page 172
 2 Notation......Page 173
 3 Some Standard Graphs......Page 174
 4 Trees......Page 176
 5 Unicyclic Graphs......Page 180
 References......Page 181
 1 Introduction......Page 183
 2 Preliminaries......Page 184
 3 Hull Number of Shadow Graphs......Page 185
 4 Geodetic Number of Shadow Graphs......Page 189
 References......Page 192
 1 Introduction......Page 194
 2 Indicated Coloring of Lexicographic Product of Graphs......Page 196
 3 Consequences of Theorem 3......Page 197
 References......Page 198
 1 Introduction......Page 200
 2 Preliminaries......Page 202
 3 Rows of Table1......Page 204
 4 The Value of (3,2)......Page 205
 5 Concluding Remarks......Page 210
 References......Page 211
 1 Introduction......Page 213
 2 Preliminaries......Page 214
 3 Proof of Theorem......Page 215
 4 Conclusion......Page 223
 References......Page 224
 1 Introduction......Page 225
 2 Convexity Number of Block Graphs......Page 227
 3 Convexity Number in Graph Products......Page 228
 4 Realizing -Number and Hull Number of Graphs......Page 229
 5 Delta Number in Graph Products......Page 232
 References......Page 234
 1 Introduction......Page 235
 2 Definitions and Notation......Page 236
 3 Preliminary Results......Page 238
 4 Cartesian Products of Signed Graphs......Page 239
 5 Signed Chromatic Number of Cartesian Products of Complete Graphs......Page 244
 6 Signed Chromatic Number of Cartesian Products of Cycles......Page 247
 References......Page 249
 1 Introduction......Page 251
 2 List Distinguishing Number of the Hypercube......Page 254
 3 List Distinguishing Number of Products of Arbitrary Graphs......Page 258
 4 List Distinguishing Number for pth Power of the Hypercube......Page 259
 References......Page 263
 1 Introduction......Page 264
 2 Generating Expressions for Complete St-Dags......Page 267
 3 Conclusions......Page 273
 References......Page 274
 1 Introduction and Main Result......Page 276
 2 Proof of Theorem 1......Page 277
 References......Page 282
Combinatorial Optimization......Page 283
 1 Introduction......Page 284
  1.1 Our Contributions......Page 286
 2 A Primal-Dual Approximation......Page 287
 3 A Combinatorial Algorithm for Solving the Dual......Page 289
 References......Page 295
 1 Introduction......Page 297
 2 Preliminaries......Page 299
  2.1 Model......Page 300
  2.2 Feasible Train Movement......Page 301
  2.3 Deadlock......Page 302
  3.1 Waiting......Page 303
  3.2 Shunting......Page 306
 4 Polynomial Time Algorithms for Paths......Page 307
 A  Difference Between Wormhole and Train Routing......Page 308
 C  Proof of Proposition 1......Page 309
 D  Deadlock Examples......Page 310
 E  Proof of Theorem 2......Page 311
 G  Proof of Theorem 5......Page 313
 H  Delaying on a Path......Page 315
 I Algorithm to Compute Waiting Times on an Uni- directional Path on Which All Trains Share One Node......Page 316
 References......Page 317
Distributed Algorithms......Page 319
 1 Introduction......Page 320
  1.1 The n-star Graph (Sn)......Page 322
  2.1 Graph Terminology......Page 323
  2.2 Cycle Structure of Permutations......Page 324
 3 The Proposed Routing Algorithm......Page 325
 4 Analysis of the Proposed Routing Algorithm......Page 328
 References......Page 330
 1 Introduction......Page 331
 2 Earlier Works......Page 332
 4 Model and Definitions......Page 333
 5 Impossibility Results......Page 336
 6 Algorithm......Page 337
 7 Correctness......Page 340
 References......Page 342
 1 Introduction......Page 344
 3 System Model......Page 345
 4 0-1 Timed Matching......Page 346
  5.1 NP-Completeness of MAX-0-1-TMB-1......Page 347
  5.2 NP-Completeness of MAX-0-1-TMT-3......Page 349
 6 Finding Maximum 0-1 Timed Matching for Rooted Temporal Tree with Single Time Interval Per Edge......Page 351
  6.1 Proof of Correctness......Page 354
 References......Page 358
 1 Introduction......Page 360
 2 Model and Definitions......Page 362
  3.1 Leader Election......Page 364
  3.2 Phase 1......Page 365
  3.3 Phase 2......Page 366
  3.4 Pattern Formation from Leader Configuration......Page 369
 4 Conclusion......Page 370
 References......Page 371
Combinatorial Algorithms......Page 373
 1 Universal Cycles for Weak Orders......Page 374
 2 Proof of Theorem 1......Page 377
 3 Proof of Theorem 2......Page 379
 References......Page 380
 1 Introduction and Model Definition......Page 382
 2 Results for the Basic Hexagonal Model......Page 383
  2.1 Homogeneous Fortification......Page 385
  2.2 Selective Fortification......Page 386
  2.3 An NP-Complete Problem......Page 391
 3 Variants of Basic Hexagonal Model......Page 392
 References......Page 393
 1 Introduction......Page 395
 2 Preliminary Definitions......Page 397
  2.2 Ties in the Preference Lists......Page 398
 3 An Algorithm for Spa-St under strong stability......Page 399
  3.1 Definitions Relating to the Algorithm......Page 400
  3.2 Description of the Algorithm......Page 402
  3.3 Example Algorithm Execution......Page 403
  3.4 Correctness of the algorithm......Page 407
 References......Page 408
Computational Complexity......Page 411
 1 Introduction......Page 412
 2 The Graphs with One Edge......Page 415
 3 Complexity of Max (k)-F-Overlay......Page 416
  4.1 Regular Graphs......Page 418
  4.2 Paths......Page 420
 References......Page 422
 1 Introduction......Page 424
 2 Preliminaries......Page 426
 4 Disjoint Paths and the Directed Subgraph Homeomorphism Problem......Page 428
 5 Other Directed Width Measures......Page 431
 6 Conclusion......Page 433
 References......Page 434
 1 Introduction......Page 436
 2 Preliminaries......Page 438
 3 The Standard Parameter......Page 440
 4 Vertex Cover and Treewidth......Page 441
 5 Concluding Remarks......Page 446
 References......Page 447
 1 Introduction......Page 448
 2 Preliminaries......Page 450
 3 FPT Algorithm for Min-q-CNCF......Page 451
  4.1 Lower Bounds for Min-q-CNCF......Page 453
  4.2 Lower Bounds for Min-q-ONCF......Page 457
 References......Page 459
Computational Geometry......Page 460
 1 Introduction......Page 461
  1.1 Preliminaries......Page 462
 2 Plane-Projecting Dimension of Complete Graphs......Page 463
 3 Plane-Projectable Graphs in R3......Page 464
 4 Relation with Linear Arboricity and Maximum Degree......Page 467
 References......Page 469
 1 Introduction......Page 471
 2 Transforming Allowable Sequences......Page 473
 3 General Max-k Sorting Problem......Page 474
 5 Max-2 Sorting Problem......Page 476
 6 Improving Lower Bounds for h"0365h(n)......Page 479
 7 Future Work......Page 481
 References......Page 482
 1 Introduction......Page 484
 2 Radon Partitions and Linear Classifiers......Page 487
 3 Algorithms for Tolerant Radon Partitions......Page 489
 4 Experimental Results......Page 492
 References......Page 494
Author Index......Page 496