Combinatorial algorithms 31st International Workshop, IWOCA 2020, Bordeaux, France, June 8-10, 2020, Proceedings /: 31st International Workshop, IWOCA 2020, Bordeaux, France, June 8-10, 2020, Proceedings. (2020)

• Record Type: Book
• Other Titles: IWOCA 2020
• Further Information: Note: Leszek Gasieniec, Ralf Klasing, Tomasz Radzik (eds.).
• Other Names: Gąsieniec, Leszek; Klasing, Ralf; Radzik, Tomasz; International Workshop on Combinatorial Algorithms, 31st
• Contents: Intro -- Preface -- Organization -- Abstracts of Invited Talks -- Optimization by Population: Large-Scale Distributed Optimization Via Population Protocols -- Coordinating Swarms of Objects at Extreme Dimensions -- Algorithms for String Processing in Restricted-Access Models of Computation -- Contents -- Invited Paper -- Coordinating Swarms of Objects at Extreme Dimensions -- 1 Introduction -- 2 Traffic -- 3 Uniform Global Control for Particle Swarms -- 4 Online Triangulation and Structured Exploration -- 5 Cohesive Control -- 6 Coordinated Motion Planning 7 Constructing and Reconfiguring Large-Scale Structures -- 8 Conclusion -- References -- Contributed Papers -- A Family of Tree-Based Generators for Bubbles in Directed Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Defining a Bubble Generator from a Spanning Tree -- 4 Experimental Results -- 4.1 An Empirical Analysis of the Characteristics of the Bubble Generator Based on the Choice of the Spanning Tree -- 4.2 Application of the Bubble Generator to the Identification of AS Events in RNA-seq Data -- 5 Conclusions and Open Problems -- References -- The Micro-world of Cographs -- 1 Introduction 2 Preliminaries -- 3 Graph Parameters -- 3.1 Co-chromatic Number -- 3.2 Lettericity -- 3.3 Boxicity -- 3.4 H-Index -- 3.5 Achromatic Number -- 4 The Hierarchy -- 5 Conclusion and Open Problems -- References -- Parameterized Complexity of (A, )-Path Packing -- 1 Introduction -- 2 Preliminaries -- 3 Standard Parameterizations of ALPP -- 3.1 Intractable Cases -- 3.2 Tractable Cases -- 4 Structural Parameterizations -- 5 Hardness on Grid Graphs -- 6 Concluding Remarks -- References -- On Proper Labellings of Graphs with Minimum Label Sum -- 1 Introduction -- 2 First Insights into the Problem 2.1 Warm-Up Results -- 2.2 Using Larger Labels can be Arbitrarily Better -- 3 Complexity Aspects -- 3.1 NP-hardness for Planar Bipartite Graphs -- 3.2 Polynomiality for Bounded-Treewidth Graphs -- 4 General Bounds -- 4.1 Upper Bounds -- 4.2 General Conjecture and Refined Bounds for Bipartite Graphs -- 5 Conclusion -- References -- Decremental Optimization of Dominating Sets Under the Reconfiguration Framework -- 1 Introduction -- 1.1 Our Problem -- 1.2 Related Results -- 1.3 Our Results -- 2 Preliminaries -- 2.1 Optimization Variant of Dominating Set Reconfiguration -- 2.2 Useful Observations 3 Polynomial-Time (In)tractability -- 3.1 PSPACE-Completeness for Several Graph Classes -- 3.2 Linear-Time Algorithms -- 4 Fixed-Parameter (In)tractability -- 4.1 FPT Algorithm for Degeneracy and Solution Size -- 4.2 FPT Algorithm for Vertex Cover Number -- References -- On the Complexity of Stackelberg Matroid Pricing Problems -- 1 Introduction -- 2 Preliminaries -- 3 Uniform Matroid -- 4 Laminar Matroid -- 5 Partition Matroid -- 6 Conclusion and Future Work -- References -- Nonexistence Certificates for Ovals in a Projective Plane of Order Ten -- 1 Introduction -- 2 Preliminaries
• Publisher Details: Cham : Springer
• Publication Date: 2020
• Extent: 1 online resource (438 p.)
• Subjects: 004.01/51; Combinatorial analysis -- Congresses; Algorithms -- Congresses; Electronic books; Electronic books
• Languages: English
• ISBNs: 9783030489663; 3030489663
• Related ISBNs: 9783030489656; 3030489655
• Access Rights: Legal Deposit; Only available on premises controlled by the deposit library and to one user at any one time; The Legal Deposit Libraries (Non-Print Works) Regulations (UK).
• Access Usage: Restricted: Printing from this resource is governed by The Legal Deposit Libraries (Non-Print Works) Regulations (UK) and UK copyright law currently in force.