Combinatorial Algorithms, 29 Workshop, IWOCA 2018

Preface......Page 6
Organization......Page 8
Invited Talks......Page 11
Some Recent New Directions in Multivariate Algorithmics......Page 12
Survey of Some Recent Near Polynomial Time Results for Parity Games”’......Page 13
Range Minimum Queries and Applications......Page 14
Contents......Page 15
 1 Introduction......Page 18
 2 Hardness of CCRP......Page 20
 4 Unit L Graph Approximation......Page 26
 References......Page 29
 1 Introduction......Page 31
  2.1 Graphs......Page 32
  2.3 Classes of Graphs......Page 33
 3 l-Critical Graphs......Page 34
 4 Unboundedness of Linear Clique-Width......Page 36
 5 Minimality......Page 39
 References......Page 41
 1 Introduction......Page 43
 3 Classes with Linear Ramsey Number......Page 45
  3.1 Claw- and Co-claw-free Graphs......Page 46
  3.2 Diamond- and Co-diamond-free Graphs......Page 47
  3.4 2K2- and Diamond-Free Graphs......Page 49
  3.5 The Class of (P4,C4, Co-claw)-Free Graphs......Page 52
  3.6 The Class of (Co-diamond, Paw, Claw)-Free Graphs......Page 53
 References......Page 54
 1 Introduction......Page 56
 2 Proof Technique......Page 59
  3.1 Forbidden Tri-Colorings of Some Subgraphs of Cn 2......Page 60
  3.2 Graph Cn 2, n 8, Is Not PCG......Page 64
  3.3 Graph Cn2, n 8, Is a Minimal Graph that Is Not PCG......Page 65
  4.1 The Wheel......Page 66
 References......Page 67
 1 Introduction......Page 69
  2.1 Fault-Tolerant Aggregate Signature......Page 70
  2.2 Cover-Free Family Constructions......Page 73
 3 Our General Unbounded Scheme......Page 75
  4.1 Nested Family for d = 1......Page 78
  4.2 Nested Family for d 2......Page 79
 References......Page 80
 1 Introduction......Page 82
  1.1 Related Work......Page 83
 2 Minimum Polygons......Page 84
  2.1 Minimum Polygons for VC-Dimension 2......Page 85
  2.2 Minimum Polygons for VC-Dimension 3......Page 86
 3 Visibility Structure......Page 87
  4.1 Naive Algorithm and Improvements......Page 89
  5.2 VC-Dimension Distribution in Random Polygons......Page 90
 References......Page 93
 1 Introduction......Page 95
 2 Preliminaries......Page 96
  3.1 Derivation of Recurrence Formulae......Page 98
  3.2 Computing Switching Points......Page 100
 4 Data Structures for Computing R(j,i) and L(j,i)......Page 102
  5.1 Computing R(j,i)......Page 104
  5.2 Main Theorem......Page 105
 References......Page 106
 1 Introduction......Page 107
 2 Fully Leafed Induced Subtrees......Page 108
 3 Computing the Leaf Function of a Graph......Page 111
 4 Fully Leafed Induced Subtrees of Trees......Page 115
 5 Perspectives......Page 117
 References......Page 118
 1 Introduction......Page 119
  2.1 Coloring......Page 121
  2.3 Leftmost Pre-embeddings......Page 122
  2.5 Ordered Coloring......Page 124
 3 Algorithm......Page 125
  4.2 Generating Random k-Split Permutations......Page 127
  4.3 k-Track Permutations......Page 128
 References......Page 130
 1 Introduction......Page 132
 2 NP-hardness......Page 135
 3 New Approximation Algorithms......Page 137
 References......Page 142
 1 Introduction......Page 145
 2 General Ternary Trees......Page 146
 3 Complete Ternary Trees......Page 150
 References......Page 156
 1 Introduction......Page 158
 2 Preliminaries......Page 159
 3 Max-Cut for Embedded 1-Planar Graphs......Page 160
  3.1 Removing the Crossings......Page 161
  3.2 The Max-Cut Algorithm......Page 162
  3.3 Correctness......Page 164
  3.4 Running Time......Page 166
 4 Conclusion and Open Problems......Page 167
 References......Page 168
 1 Introduction......Page 170
 2 Preliminaries......Page 172
  3.1 2 Club Cover(3) is NP-Complete......Page 173
  3.2 3 Club Cover(2) is NP-Complete......Page 175
 4 Hardness of Approximation......Page 178
 5 An Approximation Algorithm for Min 2 Club Cover......Page 179
 References......Page 180
 1 Introduction......Page 182
 2 Definitions and Notations......Page 183
 3 Expected Number of Distinct -Gapped Factors......Page 184
  3.2 Upper Bound for Given Frequency Vectors......Page 185
  3.3 Optimizing Jr(x,y) and K,r(x,y), for Fixed  and r......Page 186
  3.4 Optimizing G,r(x,y), for Fixed  and r......Page 187
  3.5 Optimizing the Exponent on  and r......Page 189
 4 Typical Composition Vectors of Palindromic Factors......Page 191
 5 Conclusion......Page 192
 References......Page 193
 1 Introduction......Page 194
 2 Preliminaries......Page 196
 3 Weighted Eulerian Path Problem......Page 198
 4 Elastic Linkage Problem......Page 199
 5 Traverse Problem of a Tree by a Path......Page 201
 References......Page 205
 1 Introduction......Page 206
 3 The IPO Family of Algorithms......Page 207
  3.1 Tie-Breakers......Page 209
  3.3 Parameter Ordering......Page 210
  4.1 Setup......Page 211
  4.2 Results......Page 212
  4.3 665534 (t=3)......Page 214
 References......Page 216
 1 Introduction......Page 218
 2 Preliminaries......Page 219
 3 Enumeration by Binary Partition......Page 220
 4 Induced Subgraph Enumeration......Page 223
 5 Subgraph Enumeration......Page 226
 References......Page 229
 1 Introduction......Page 231
 2 Related Work......Page 233
 3 Online Algorithm......Page 234
 4 Competitive Analysis......Page 236
 5 Open Problems......Page 238
 References......Page 239
 1 Introduction......Page 241
 3 3-Cycle Theorem......Page 242
  3.1 Definitions and Properties......Page 243
  3.2 Proof of the 3-Cycle Theorem......Page 244
 4 Link with the 3-Hitting Set Problem......Page 249
 5 Perspectives......Page 251
 References......Page 252
 1 Introduction......Page 254
 2 Problem Definitions and Notation......Page 256
 3 A Simple FPT Algorithm for MEC......Page 257
 4 An Improved Kernel for MEC on Trees......Page 259
 5 Structural Parameterization: Vertex Cover......Page 262
 References......Page 265
 1 Introduction......Page 267
  2.1 Definitions of Card-Based Protocols......Page 269
  2.2 Six-Card AND Protocol......Page 271
  3.1 Example of Our Diagram......Page 272
  4.1 Classification of Rearrangement Error......Page 274
  4.2 Correctness and Security of Erroneous Protocols......Page 275
  5.1 Detection with Card Arrangement......Page 276
  6.1 Card Arrangement Without Rearrangement......Page 277
 References......Page 278
 1 Introduction......Page 280
 3 Zero-Suppressed Branching Programs......Page 282
  3.1 Constant-Width Zero-Suppressed Branching Programs......Page 283
  3.3 Read-Once Zero-Suppressed Branching Programs......Page 284
  4.1 Zero-Suppressed Decision Trees......Page 286
  4.2 Boolean Formulas with Zero-Suppression......Page 287
 5 Conclusions......Page 288
 References......Page 289
 1 Introduction......Page 290
 2 Preliminaries......Page 291
 3 Seq-Shellability......Page 294
  3.1 Simple Sequences......Page 295
  3.2 Seq-Shellable Drawings......Page 297
 4 Conclusion......Page 300
 References......Page 301
 1 Introduction......Page 302
  2.1 Concepts......Page 304
  2.2 Learning Models......Page 305
 3 Polynomial-Time a Posteriori Query Learnability......Page 306
  3.1 Polynomial Representation of Signatures......Page 307
  3.2 Positive Results......Page 308
  3.3 Negative Results......Page 310
  3.4 Learnability of Some Natural Classes......Page 312
 References......Page 313
 1 Introduction......Page 315
  1.1 Bioinformatics Use......Page 316
  2.1 Minimum Tracks Required for Non-overlapping Placement......Page 317
 3 Maximize Within-Track Separation......Page 318
 4 Threshold Requirement to Inter-center Distances......Page 319
 5 Maximize Sum of Inter-center Distances......Page 322
 6 Balanced Placement of Segments on Tracks......Page 324
 References......Page 326
 1 Introduction......Page 328
 2 Problem Description......Page 329
 3 Algorithm......Page 330
 4 Computational Results......Page 337
 5 Conclusion......Page 338
 References......Page 339
 1 Introduction......Page 340
  2.1 Notation......Page 341
  2.2 -balanced Grammars......Page 342
 3 LZ-ABT: Online -balanced Grammar Compression......Page 343
  3.1 Behavior of LZ-ABT with Varying......Page 344
  3.2 Implementation with Patricia Trees and Its Analysis......Page 346
  3.3 LZ-ABT in Compressed Space......Page 347
 4 Experiments......Page 348
 5 Conclusions and Future Work......Page 350
 References......Page 351
 1 Introduction......Page 353
  1.1 Our Contribution......Page 355
  1.2 Related Work......Page 356
 2 Preliminaries......Page 357
 3 Faster Coreset Construction for Subspace Clustering......Page 360
 4 Faster Coreset Construction for Projective Clustering......Page 361
 5 Conclusion and Open Problems......Page 363
 References......Page 364
 1 Introduction......Page 366
  1.1 Locating and Detecting Arrays......Page 368
 2 The Need for Separation......Page 369
 3 Randomized and Derandomized Algorithms......Page 370
  3.1 The Stein-Lovász-Johnson Framework and Conditional Expectation......Page 371
  3.2 The Lovász Local Lemma and Moser-Tardos Resampling......Page 372
 4 Some Computational Results......Page 373
 References......Page 376
 1 Introduction......Page 378
  2.1 Conjugate of a Monotonic Sequence......Page 380
  2.2 Partitions of Integers......Page 381
 3 Data Structures to Represent Monotonic Sequences......Page 382
 4 A Data Structure for Prefix Sums......Page 385
 5 A Data Structure for a Partition of an Integer......Page 386
 6 Conclusion......Page 389
 References......Page 390
 1 Introduction......Page 391
  1.1 Around the Average Solution Value......Page 392
  1.2 Outline......Page 393
 2 Seeking Symmetries in the Solution Set......Page 394
  2.2 Solution Multisets Derived from Orthogonal Arrays......Page 395
  3.1 From an Alphabet Size to a Greater One......Page 397
  3.2 Deriving Bounds from Orthogonal Arrays of the Litterature......Page 398
 4 Concluding Remarks......Page 400
 References......Page 402
Author Index......Page 404