Vai al contenuto principale della pagina

Combinatorial algorithms [electronic resource] : 31st International Workshop, IWOCA 2020, Bordeaux, France, June 8-10, 2020, Proceedings / Leszek Gasieniec, Ralf Klasing, Tomasz Radzik (eds.).



(Visualizza formato Marc21)    (visualizza in BIBRAME 2.0)

Creatore: International Workshop on Combinatorial Algorithms (31st : 2020 : Online)
Titolo: Combinatorial algorithms [electronic resource] : 31st International Workshop, IWOCA 2020, Bordeaux, France, June 8-10, 2020, Proceedings / Leszek Gasieniec, Ralf Klasing, Tomasz Radzik (eds.).
Link to work: Combinatorial algorithms Visualizza cluster
Pubblicazione: Cham : Springer, 2020
Estensione: 1 online resource (438 p.).
Tipo formato: computer
Tipo contenuto: text
Tipo supporto: online resource
Disciplina: 004.01/51
Titolo uniforme di collana: Lecture notes in computer science ; 12126.
Lecture notes in computer science. Advanced research in computing and software science.
LNCS sublibrary. SL 1, Theoretical computer science and general issues.
Classificazione LOC: QA164 .I58 2020eb
Creatori/Collaboratori: Gąsieniec, Leszek
Klasing, Ralf
Radzik, Tomasz
Note generali: International conference proceedings.
Title page lists location as Bordeaux, France but the preface states "The symposium was run online on the originally set dates of 8-0 June 2020".
Description based upon print version of record.
2.1 Projective Geometry
Includes author index.
Nota di contenuto: 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
Sommario/riassunto: This book constitutes the proceedings of the 31st International Workshop on Combinatorial Algorithms which was planned to take place in Bordeaux, France, during June 8-10, 2020. Due to the COVID-19 pandemic the conference changed to a virtual format. The 30 full papers included in this book were carefully reviewed and selected from 62 submissions. They focus on algorithms design for the myriad of combinatorial problems that underlie computer applications in science, engineering and business.
Collana: Lecture Notes in Computer Science ; 12126
Advanced Research in Computing and Software Science
LNCS Sublibrary: SL 1, Theoretical Computer Science and General Issues
Varianti del titolo: IWOCA 2020
ISBN: 9783030489663
3030489663
9783030489656
3030489655
Formato: Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione: Inglese
Record Nr.: a13630366
Localizzazioni e accesso elettronico https://stanford.idm.oclc.org/login?url=http://link.springer.com/10.1007/978-3-030-48966-3
Lo trovi qui: Stanford University
Item: Permalink to OPAC
Altra ed. diverso supporto: Print version: Gąsieniec, Leszek Combinatorial Algorithms : 31st International Workshop, IWOCA 2020, Bordeaux, France, June 8-10, 2020, Proceedings Cham : Springer International Publishing AG, c2020 9783030489656