Info
- Utilizzare la checkbox di selezione a fianco di ciascun documento per attivare le funzionalità di stampa, invio email, download nei formati disponibili del (i) record.
Algorithms for sensor systems : 17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2021, Lisbon, Portugal, September 9-10, 2021, proceedings / / Leszek Ga̜sieniec, Ralf Klasing, Tomasz Radzik (editors)
| Algorithms for sensor systems : 17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2021, Lisbon, Portugal, September 9-10, 2021, proceedings / / Leszek Ga̜sieniec, Ralf Klasing, Tomasz Radzik (editors) |
| Pubbl/distr/stampa | Cham, Switzerland : , : Springer, , [2021] |
| Descrizione fisica | 1 online resource (166 pages) |
| Disciplina | 681 |
| Collana | Lecture Notes in Computer Science |
| Soggetto topico | Wireless sensor networks |
| ISBN | 3-030-89240-9 |
| Formato | Materiale a stampa  |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Intro -- Preface -- Organization -- Universally-Optimal Distributed Algorithms, (Congestion+Dilation)-Competitive Oblivious Routing, and Hop-Constrained Network Design (Abstract of Invited Talk) -- Contents -- Distributed Transformations of Hamiltonian Shapes Based on Line Moves -- 1 Introduction -- 1.1 Related Work -- 1.2 Our Contribution -- 2 Model -- 3 The Distributed Hamiltonian Transformation -- References -- Stand up Indulgent Gathering -- 1 Introduction -- 2 Model -- 3 The SUIG Algorithm -- 4 Concluding Remarks -- References -- Gathering a Euclidean Closed Chain of Robots in Linear Time -- 1 Introduction -- 2 Model and Notation -- 3 Basics -- 3.1 Isogonal Configurations -- 3.2 Sequential Movement with Run-States -- 4 Closed-Chain-Hopper -- 4.1 Intuition About the Asymmetric Algorithm -- 4.2 Asymmetric Algorithm in Detail -- 4.3 Symmetric Algorithm -- 4.4 Combination of the Algorithms -- 4.5 Analysis Sketch -- 5 Concluding Remarks -- References -- Centralised Connectivity-Preserving Transformations for Programmable Matter: A Minimal Seed Approach -- 1 Introduction -- 2 Contribution -- 3 Model -- 4 Infeasible Transformations and the Time Lower Bound -- 4.1 Time and Seed Lower Bounds for Line Transformations -- 5 Transformation for Nice Shapes -- 5.1 Line to Nice Shape -- 5.2 RaiseNodes -- 5.3 MirrorSeed -- 5.4 DepositNode -- 5.5 Construction of a Subset of Nice Shapes -- 5.6 Construction of Any Nice Shape -- 6 Conclusions -- References -- Distributed Coloring and the Local Structure of Unit-Disk Graphs -- 1 Introduction -- 2 Preliminaries -- 2.1 Distributed Models of Communication -- 2.2 Distributed Coloring -- 2.3 Unit-Disk Graphs -- 3 Location-Aware Coloring -- 4 Coloring Without Coordinates -- 5 Conclusion -- References -- Evacuating from p Unit Disks in the Wireless Model -- 1 Introduction -- 1.1 Related Work.
1.2 High Level of New Contributions and Motivation -- 2 Problem Definition, Notation and Nomenclature -- 3 Algorithms for Evacuating 2 Robots in p Spaces -- 3.1 Worst Case Analysis of Algorithm Wireless-Searchp() -- 4 Visualization of Key Concepts and Results -- 5 Lower Bounds and the Proof of Theorem 1 -- 6 Discussion -- References -- Beep-And-Sleep: Message and Energy Efficient Set Cover -- 1 Introduction -- 1.1 Related Work -- 1.2 Structure of This Paper -- 2 An Efficient SetCover-Algorithm for the Beeping-Model -- 2.1 Proof of Theorem 1 -- 2.2 Extension to DominatingSet -- 3 A Low-Message KT_0 Algorithm -- 3.1 Proof of Theorem 2 -- 3.2 Lower Bound -- 4 Conclusion and Future Work -- References -- Byzantine Fault Tolerant Symmetric-Persistent Circle Evacuation -- 1 Introduction -- 1.1 Model and Preliminaries -- 1.2 Related Work -- 1.3 Results of the Paper -- 2 Evacuation with One Byzantine Fault -- 2.1 Lower Bound for Symmetric-Persistent Algorithms -- 3 Evacuation with Two Byzantine Faults -- 3.1 Algorithm for (n,2) - Evacuation -- 4 Conclusion -- A Appendix - (n) Calculation -- References -- Overflow Management with Self-eliminations -- 1 Introduction -- 2 Model Definition -- 3 Algorithms and Competitive Analysis -- 4 Simulation Results -- 5 Conclusion and Open Questions -- References -- Population Protocols with Unreliable Communication -- 1 Introduction -- 1.1 Main Results (Preview) -- 2 Basic Definitions -- 2.1 Protocols -- 2.2 Fair Executions -- 2.3 Functions Implemented by Protocols -- 3 Expressive Power of Population Protocols and Related Models -- 4 Our Models -- 4.1 Proposed Models -- 4.2 The Main Result -- 5 Proof of the Main Result -- 6 Non-monotonic Impact of Unreliability -- 7 Conclusion and Future Directions -- References -- Author Index. |
| Record Nr. | UNISA-996464432303316 |
| Cham, Switzerland : , : Springer, , [2021] | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Algorithms for sensor systems : 17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2021, Lisbon, Portugal, September 9-10, 2021, proceedings / / Leszek Ga̜sieniec, Ralf Klasing, Tomasz Radzik (editors)
| Algorithms for sensor systems : 17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2021, Lisbon, Portugal, September 9-10, 2021, proceedings / / Leszek Ga̜sieniec, Ralf Klasing, Tomasz Radzik (editors) |
| Pubbl/distr/stampa | Cham, Switzerland : , : Springer, , [2021] |
| Descrizione fisica | 1 online resource (166 pages) |
| Disciplina | 681 |
| Collana | Lecture Notes in Computer Science |
| Soggetto topico | Wireless sensor networks |
| ISBN | 3-030-89240-9 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Intro -- Preface -- Organization -- Universally-Optimal Distributed Algorithms, (Congestion+Dilation)-Competitive Oblivious Routing, and Hop-Constrained Network Design (Abstract of Invited Talk) -- Contents -- Distributed Transformations of Hamiltonian Shapes Based on Line Moves -- 1 Introduction -- 1.1 Related Work -- 1.2 Our Contribution -- 2 Model -- 3 The Distributed Hamiltonian Transformation -- References -- Stand up Indulgent Gathering -- 1 Introduction -- 2 Model -- 3 The SUIG Algorithm -- 4 Concluding Remarks -- References -- Gathering a Euclidean Closed Chain of Robots in Linear Time -- 1 Introduction -- 2 Model and Notation -- 3 Basics -- 3.1 Isogonal Configurations -- 3.2 Sequential Movement with Run-States -- 4 Closed-Chain-Hopper -- 4.1 Intuition About the Asymmetric Algorithm -- 4.2 Asymmetric Algorithm in Detail -- 4.3 Symmetric Algorithm -- 4.4 Combination of the Algorithms -- 4.5 Analysis Sketch -- 5 Concluding Remarks -- References -- Centralised Connectivity-Preserving Transformations for Programmable Matter: A Minimal Seed Approach -- 1 Introduction -- 2 Contribution -- 3 Model -- 4 Infeasible Transformations and the Time Lower Bound -- 4.1 Time and Seed Lower Bounds for Line Transformations -- 5 Transformation for Nice Shapes -- 5.1 Line to Nice Shape -- 5.2 RaiseNodes -- 5.3 MirrorSeed -- 5.4 DepositNode -- 5.5 Construction of a Subset of Nice Shapes -- 5.6 Construction of Any Nice Shape -- 6 Conclusions -- References -- Distributed Coloring and the Local Structure of Unit-Disk Graphs -- 1 Introduction -- 2 Preliminaries -- 2.1 Distributed Models of Communication -- 2.2 Distributed Coloring -- 2.3 Unit-Disk Graphs -- 3 Location-Aware Coloring -- 4 Coloring Without Coordinates -- 5 Conclusion -- References -- Evacuating from p Unit Disks in the Wireless Model -- 1 Introduction -- 1.1 Related Work.
1.2 High Level of New Contributions and Motivation -- 2 Problem Definition, Notation and Nomenclature -- 3 Algorithms for Evacuating 2 Robots in p Spaces -- 3.1 Worst Case Analysis of Algorithm Wireless-Searchp() -- 4 Visualization of Key Concepts and Results -- 5 Lower Bounds and the Proof of Theorem 1 -- 6 Discussion -- References -- Beep-And-Sleep: Message and Energy Efficient Set Cover -- 1 Introduction -- 1.1 Related Work -- 1.2 Structure of This Paper -- 2 An Efficient SetCover-Algorithm for the Beeping-Model -- 2.1 Proof of Theorem 1 -- 2.2 Extension to DominatingSet -- 3 A Low-Message KT_0 Algorithm -- 3.1 Proof of Theorem 2 -- 3.2 Lower Bound -- 4 Conclusion and Future Work -- References -- Byzantine Fault Tolerant Symmetric-Persistent Circle Evacuation -- 1 Introduction -- 1.1 Model and Preliminaries -- 1.2 Related Work -- 1.3 Results of the Paper -- 2 Evacuation with One Byzantine Fault -- 2.1 Lower Bound for Symmetric-Persistent Algorithms -- 3 Evacuation with Two Byzantine Faults -- 3.1 Algorithm for (n,2) - Evacuation -- 4 Conclusion -- A Appendix - (n) Calculation -- References -- Overflow Management with Self-eliminations -- 1 Introduction -- 2 Model Definition -- 3 Algorithms and Competitive Analysis -- 4 Simulation Results -- 5 Conclusion and Open Questions -- References -- Population Protocols with Unreliable Communication -- 1 Introduction -- 1.1 Main Results (Preview) -- 2 Basic Definitions -- 2.1 Protocols -- 2.2 Fair Executions -- 2.3 Functions Implemented by Protocols -- 3 Expressive Power of Population Protocols and Related Models -- 4 Our Models -- 4.1 Proposed Models -- 4.2 The Main Result -- 5 Proof of the Main Result -- 6 Non-monotonic Impact of Unreliability -- 7 Conclusion and Future Directions -- References -- Author Index. |
| Record Nr. | UNINA-9910506394903321 |
| Cham, Switzerland : , : Springer, , [2021] | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Algorithms for Sensor Systems [[electronic resource] ] : 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015, Patras, Greece, September 17-18, 2015, Revised Selected Papers / / edited by Prosenjit Bose, Leszek Antoni Gąsieniec, Kay Römer, Roger Wattenhofer
| Algorithms for Sensor Systems [[electronic resource] ] : 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015, Patras, Greece, September 17-18, 2015, Revised Selected Papers / / edited by Prosenjit Bose, Leszek Antoni Gąsieniec, Kay Römer, Roger Wattenhofer |
| Edizione | [1st ed. 2015.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015 |
| Descrizione fisica | 1 online resource (XIV, 225 p. 19 illus. in color.) |
| Disciplina | 681.2 |
| Collana | Computer Communication Networks and Telecommunications |
| Soggetto topico |
Algorithms
Computers Computer communication systems Computer science—Mathematics Artificial intelligence Application software Algorithm Analysis and Problem Complexity Computation by Abstract Devices Computer Communication Networks Mathematics of Computing Artificial Intelligence Information Systems Applications (incl. Internet) |
| ISBN | 3-319-28472-X |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Plane and Planarity Thresholds for Random Geometric Graphs -- Connectivity of a dense mesh of randomly oriented directional antennas under a realistic fading model -- Maintaining Intruder Detection Capability in a Rectangular Domain with Sensors -- The Weakest Oracle for Symmetric Consensus in Population Protocols -- Exact and Approximation Algorithms for Data Mule Scheduling in a Sensor Network -- Limitations of Current Wireless Scheduling Algorithms -- Deterministic rendezvous with detection using beeps -- Minimizing total sensor movement for barrier coverage by non-uniform sensors on a line -- A comprehensive and lightweight security architecture to secure the IoT throughout the lifecycle of a device based on HIMMO -- Maximizing Throughput in Energy-Harvesting Sensor Nodes -- On verifying and maintaining connectivity of interval temporal networks -- Beachcombing on Strips and Islands -- Radio Aggregation Scheduling -- Gathering of Robots on Meeting-Points -- Mutual Visibility with an Optimal Number of Colors -- Mobile Agents Rendezvous in spite of a Malicious Agent. . |
| Record Nr. | UNISA-996466361403316 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Algorithms for Sensor Systems : 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015, Patras, Greece, September 17-18, 2015, Revised Selected Papers / / edited by Prosenjit Bose, Leszek Antoni Gąsieniec, Kay Römer, Roger Wattenhofer
| Algorithms for Sensor Systems : 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015, Patras, Greece, September 17-18, 2015, Revised Selected Papers / / edited by Prosenjit Bose, Leszek Antoni Gąsieniec, Kay Römer, Roger Wattenhofer |
| Edizione | [1st ed. 2015.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015 |
| Descrizione fisica | 1 online resource (XIV, 225 p. 19 illus. in color.) |
| Disciplina | 681.2 |
| Collana | Computer Communication Networks and Telecommunications |
| Soggetto topico |
Algorithms
Computers Computer communication systems Computer science—Mathematics Artificial intelligence Application software Algorithm Analysis and Problem Complexity Computation by Abstract Devices Computer Communication Networks Mathematics of Computing Artificial Intelligence Information Systems Applications (incl. Internet) |
| ISBN | 3-319-28472-X |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Plane and Planarity Thresholds for Random Geometric Graphs -- Connectivity of a dense mesh of randomly oriented directional antennas under a realistic fading model -- Maintaining Intruder Detection Capability in a Rectangular Domain with Sensors -- The Weakest Oracle for Symmetric Consensus in Population Protocols -- Exact and Approximation Algorithms for Data Mule Scheduling in a Sensor Network -- Limitations of Current Wireless Scheduling Algorithms -- Deterministic rendezvous with detection using beeps -- Minimizing total sensor movement for barrier coverage by non-uniform sensors on a line -- A comprehensive and lightweight security architecture to secure the IoT throughout the lifecycle of a device based on HIMMO -- Maximizing Throughput in Energy-Harvesting Sensor Nodes -- On verifying and maintaining connectivity of interval temporal networks -- Beachcombing on Strips and Islands -- Radio Aggregation Scheduling -- Gathering of Robots on Meeting-Points -- Mutual Visibility with an Optimal Number of Colors -- Mobile Agents Rendezvous in spite of a Malicious Agent. . |
| Record Nr. | UNINA-9910484507903321 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Fundamentals of Computation Theory [[electronic resource] ] : 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14, 2019, Proceedings / / edited by Leszek Antoni Gąsieniec, Jesper Jansson, Christos Levcopoulos
| Fundamentals of Computation Theory [[electronic resource] ] : 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14, 2019, Proceedings / / edited by Leszek Antoni Gąsieniec, Jesper Jansson, Christos Levcopoulos |
| Edizione | [1st ed. 2019.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2019 |
| Descrizione fisica | 1 online resource (XIII, 365 p. 266 illus., 27 illus. in color.) |
| Disciplina | 004.015113 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Algorithms
Computer graphics Computer science—Mathematics Discrete mathematics Artificial intelligence Artificial intelligence—Data processing Computer networks Computer Graphics Discrete Mathematics in Computer Science Artificial Intelligence Data Science Computer Communication Networks |
| ISBN | 3-030-25027-X |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Invited papers -- Algebraic Theory of Promise Constraint Satisfaction Problems, First Steps -- Some Observations on Dynamic Random Walks and Network Renormalization -- Highly Succinct Dynamic Data Structures -- Formal methods -- Largest Common Prefix of a Regular Tree Language -- Winning Strategies for Streaming Rewriting Games -- Nominal Syntax with Atom Substitutions: Matching, Unification, Rewriting -- Two characterizations of finite-state dimension -- Complexity -- Optimal channel utilization with limited feedback -- Deterministic Preparation of Dicke States -- Complete Disjoint coNP-Pairs but no Complete Total Polynomial Search Problems Relative to an Oracle -- On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties -- Algorithms -- An Efficient Algorithm for the Fast Delivery Problem -- Extension of some edge graph problems: standard and parameterized complexity -- Space Efficient Algorithms for Breadth-Depth Search -- Circular Pattern Matching with k Mismatches -- Succinct Representations of Finite Groups -- On the Tractability of Covering a Graph with 2-Clubs -- On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest -- Maximum rectilinear convex subsets -- Computing Digraph Width Measures on Directed Co-Graphs -- Fault-tolerant parallel scheduling of arbitrary length jobs on a shared channel -- Rare Siblings Speed-up Deterministic Detection and Counting of Small Pattern Graphs -- Bivariate B-splines from convex pseudo-circle configurations -- The Fault-Tolerant Metric Dimension of Cographs. |
| Record Nr. | UNISA-996466443403316 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2019 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Fundamentals of Computation Theory : 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14, 2019, Proceedings / / edited by Leszek Antoni Gąsieniec, Jesper Jansson, Christos Levcopoulos
| Fundamentals of Computation Theory : 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14, 2019, Proceedings / / edited by Leszek Antoni Gąsieniec, Jesper Jansson, Christos Levcopoulos |
| Edizione | [1st ed. 2019.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2019 |
| Descrizione fisica | 1 online resource (XIII, 365 p. 266 illus., 27 illus. in color.) |
| Disciplina |
004.015113
004 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Algorithms
Computer graphics Computer science—Mathematics Discrete mathematics Artificial intelligence Artificial intelligence—Data processing Computer networks Computer Graphics Discrete Mathematics in Computer Science Artificial Intelligence Data Science Computer Communication Networks |
| ISBN | 3-030-25027-X |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Invited papers -- Algebraic Theory of Promise Constraint Satisfaction Problems, First Steps -- Some Observations on Dynamic Random Walks and Network Renormalization -- Highly Succinct Dynamic Data Structures -- Formal methods -- Largest Common Prefix of a Regular Tree Language -- Winning Strategies for Streaming Rewriting Games -- Nominal Syntax with Atom Substitutions: Matching, Unification, Rewriting -- Two characterizations of finite-state dimension -- Complexity -- Optimal channel utilization with limited feedback -- Deterministic Preparation of Dicke States -- Complete Disjoint coNP-Pairs but no Complete Total Polynomial Search Problems Relative to an Oracle -- On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties -- Algorithms -- An Efficient Algorithm for the Fast Delivery Problem -- Extension of some edge graph problems: standard and parameterized complexity -- Space Efficient Algorithms for Breadth-Depth Search -- Circular Pattern Matching with k Mismatches -- Succinct Representations of Finite Groups -- On the Tractability of Covering a Graph with 2-Clubs -- On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest -- Maximum rectilinear convex subsets -- Computing Digraph Width Measures on Directed Co-Graphs -- Fault-tolerant parallel scheduling of arbitrary length jobs on a shared channel -- Rare Siblings Speed-up Deterministic Detection and Counting of Small Pattern Graphs -- Bivariate B-splines from convex pseudo-circle configurations -- The Fault-Tolerant Metric Dimension of Cographs. |
| Record Nr. | UNINA-9910349307903321 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2019 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
SOFSEM 2023, theory and practice of computer science : 48th international conference on current trends in theory and practice of computer science, SOFSEM 2023, Nový Smokovec, Slovakia, January 15-18, 2023, proceedings / / edited by Leszek Gąsieniec
| SOFSEM 2023, theory and practice of computer science : 48th international conference on current trends in theory and practice of computer science, SOFSEM 2023, Nový Smokovec, Slovakia, January 15-18, 2023, proceedings / / edited by Leszek Gąsieniec |
| Pubbl/distr/stampa | Cham, Switzerland : , : Springer, , [2023] |
| Descrizione fisica | 1 online resource (401 pages) |
| Disciplina | 004 |
| Collana | Lecture Notes in Computer Science |
| Soggetto topico | Computer science |
| ISBN |
9783031231018
9783031231001 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Intro -- Preface -- Organization -- Contents -- Graphs Problems and Optimisation -- The Complexity of Finding Tangles -- 1 Introduction -- 2 Exact Algorithms -- 3 Complexity -- 4 Counterexample to Conjecture 1 -- References -- A Spectral Algorithm for Finding Maximum Cliques in Dense Random Intersection Graphs -- 1 Introduction -- 1.1 Previous Work on Maximum Cliques in Random Intersection Graphs -- 2 Our Contribution -- 3 Definitions, Notation and Useful Results -- 3.1 Range of Values for m,n,p -- 4 The Spectral Algorithm -- 4.1 Running Time of Our Algorithm -- 5 Experimental Evaluation -- 6 Conclusions -- 7 Appendix -- 7.1 Greedy-Clique Algorithm -- 7.2 Mono-Clique Algorithm -- 7.3 Maximum-Clique Algorithm -- References -- Solving Cut-Problems in Quadratic Time for Graphs with Bounded Treewidth -- 1 Introduction -- 2 Related Work -- 3 Preliminaries -- 4 Max-Bisection: From O(2t n3) to O(2tn2) -- 5 Our Framework -- 6 Conclusion -- References -- More Effort Towards Multiagent Knapsack -- 1 Introduction -- 2 Hardness of Median-UK -- 3 Algorithms for Special Cases -- 3.1 When = 1: Diverse Knapsack -- 4 Conclusion -- References -- Graph Drawing and Visualization -- Dominance Drawings for DAGs with Bounded Modular Width -- 1 Introduction -- 2 Preliminaries -- 3 The Compaction Lemma -- 4 Minimizing the Number of Fips -- 5 Minimizing the Number of Dimensions -- 6 Concluding Remarks -- References -- Morphing Planar Graph Drawings Through 3D -- 1 Introduction -- 2 An Upper Bound -- 2.1 3D Morph Operations -- 2.2 3D Morphs for Biconnected Planar Graphs -- 2.3 3D Morphs for General Planar Graphs -- 3 Discussion: Lower Bounds -- 4 Open Problems -- References -- Visualizing Multispecies Coalescent Trees: Drawing Gene Trees Inside Species Trees -- 1 Introduction -- 2 Drawing Style -- 3 NP-Hardness -- 4 Planar Instances -- 5 Algorithms -- References.
Parameterized Approaches to Orthogonal Compaction -- 1 Introduction -- 2 Basic Definitions -- 3 Number of Kitty Corners: An FPT Algorithm -- 4 A Polynomial Kernel for Cycle Graphs -- 5 Maximum Face Degree: Parameterized Hardness -- 6 Height of the Representation: An XP Algorithm -- 7 Open Problems -- References -- NP-Hardness and Fixed Parameter Tractability -- Hardness of Bounding Influence via Graph Modification -- 1 Introduction -- 2 Related Work -- 3 Preliminaries -- 3.1 Graph Theoretic Terminology -- 3.2 Centrality Measures -- 4 Bounding the Influence of Vertex Centrality Scores -- References -- Heuristics for Opinion Diffusion via Local Elections -- 1 Introduction -- 1.1 Our Contributions -- 1.2 Related Work -- 2 Formal Model -- 2.1 Opinion Graphs -- 2.2 Campaigning and Bribery -- 2.3 Diffusion Processes via Local Elections -- 2.4 Election Results via Global Voting Rules -- 2.5 Optimization Goals -- 3 Computing Optimal Bribery Schemes -- 3.1 Heuristic Methods -- 4 Simulations -- 4.1 Experimental Design -- 4.2 Results -- 5 Outlook -- References -- On the Parameterized Complexity of s-club Cluster Deletion Problems -- 1 Introduction -- 2 Preliminaries -- 3 Algorithm for s-Club Cluster Edge Deletion -- 3.1 Definition of the Records -- 3.2 Description of the Algorithm -- 4 Algorithm for s-Club Cluster Vertex Deletion -- 5 Discussion and Open Problems -- References -- SOFSEM 2023 Best Papers -- Balanced Substructures in Bicolored Graphs -- 1 Introduction -- 2 NP-hardness Results -- 2.1 Complexity in Split Graphs -- 3 Small Balanced Paths, Trees and Connected Subgraphs -- 4 FPT Algorithms -- 4.1 Randomized Algorithms -- 4.2 Deterministic Algorithms -- 5 Concluding Remarks -- References -- On the Complexity of Scheduling Problems with a Fixed Number of Parallel Identical Machines -- 1 Introduction -- 2 Preliminaries -- 2.1 Subset Sum and Partition. 2.2 Scheduling -- 2.3 The Scheduling Lower Bounds by Abboud et al. -- 2.4 Our Results -- 3 Problems with One Machine -- 4 Problems with Multiple Machines -- 5 Conclusion -- References -- SOFSEM 2023 Best Student Papers -- On the 2-Layer Window Width Minimization Problem -- 1 Introduction -- 2 Window Width Minimization with Bottom Layer Fixed -- 3 Window Width Minimization with Top Layer Fixed -- 4 Open Problems -- References -- Sequentially Swapping Tokens: Further on Graph Classes -- 1 Introduction -- 2 Preliminaries -- 3 Polynomial-Time Algorithm for Block-Cactus Graphs -- 3.1 Reduction to a Generalized Problem on Biconnected Components -- 3.2 Sub-STS on cycles -- 3.3 Sub-STS on complete graphs -- 3.4 The Whole Algorithm -- 4 Hardness of the Few-Color and Colorful Cases -- 4.1 General Tools for Showing Hardness -- 4.2 The Few-Color Case on Grid-Like Graphs -- 4.3 The Colorful Case on Grid-Like Graphs -- 5 Concluding Remarks -- References -- Communication and Temporal Graphs -- On the Preservation of Properties When Changing Communication Models -- 1 Introduction -- 2 The FIFO System -- 3 Comparing Channel Layouts -- 4 Property Preservation -- 4.1 Reachability -- 4.2 Deadlock Freedom -- 4.3 Confluence -- 4.4 Summary of Results -- 5 Conclusion -- References -- Introduction to Routing Problems with Mandatory Transitions -- 1 Introduction -- 2 Shortest Path Problems with Mandatory Transitions -- 2.1 Polynomiality of SPMT -- 2.2 Non Approximation of Elementary SPMTand MRMT -- 3 Routing Problems with Mandatory Transitions -- 4 Conclusion -- References -- Payment Scheduling in the Interval Debt Model -- 1 Introduction -- 2 The Interval Debt Model -- 2.1 Formal Setting -- 2.2 Schedules -- 2.3 Problem Definitions -- 3 Our Results -- 3.1 Hardness Results -- 3.2 Polynomial-Time Algorithms -- 4 Conclusion and Open Problems -- References. Multi-Parameter Analysis of Finding Minors and Subgraphs in Edge-Periodic Temporal Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Temporal Extension of Graph Problems -- 4 Periodic Character Alignment -- 5 Minors and Subgraphs -- 5.1 Subgraphs -- 5.2 Minors -- 5.3 Further Parameterized Analysis -- 6 Short Traversal -- 7 Conclusion -- References -- Complexity and Learning -- Lower Bounds for Monotone q-Multilinear Boolean Circuits -- 1 Introduction -- 2 Monotone Boolean Circuits and Functions -- 3 Monotone q-multilinear Boolean Circuits -- 3.1 q-multilinearity Versus Bounded Conjunction Depth -- 4 Lower Bounds for q-multilinear Boolean Circuits -- 4.1 Lower Bound Trade-Offs for Semi-disjoint Bilinear Forms -- 4.2 Lower Bounds for Isolk,n -- References -- A Faster Algorithm for Determining the Linear Feasibility of Systems of BTVPI Constraints -- 1 Introduction -- 2 Statement of Problems -- 3 A Rewrite Version of Fourier-Motzkin Elimination -- 4 The BCS Linear Programming Algorithm -- 4.1 Analysis -- 5 Conclusion -- References -- Quantum Complexity for Vector Domination Problem -- 1 Introduction -- 1.1 Prior Work -- 1.2 Our Results -- 2 Preliminaries -- 2.1 Problem Definitions -- 2.2 Quantum Query Model -- 2.3 Techniques -- 3 Vector Domination -- 3.1 Lower Bounds -- 3.2 Upper Bounds -- 4 Minimum Inner Product -- 4.1 Idea -- 4.2 Preprocessing -- 4.3 Reduction -- 5 Open Questions -- References -- Learning Through Imitation by Using Formal Verification -- 1 Introduction -- 2 Related Work -- 3 Method -- 3.1 Q-Learning -- 3.2 Using a Model Checker on the Q-learning Model -- 4 Model Checker as an Expert-Applications -- 4.1 Convergence with Fewer Epochs -- 4.2 Help Convergence by Avoiding Sub-optimal Solutions -- 4.3 Explore Unseen States -- 5 Discussion -- References -- Robots and Strings -- Delivery to Safety with Two Cooperating Robots -- 1 Introduction. 1.1 Model, Notation, and Preliminaries -- 1.2 Related Work -- 1.3 Outline and Results of the Paper -- 2 Optimal Offline Algorithm -- 3 Online Algorithm for the OneAxis Model -- 4 Online Algorithms for the NoAxis Model -- 4.1 VisibleBoundary Model -- 4.2 DiscoverableBoundary Model -- 4.3 InvisibleBoundary Model -- 5 Conclusion -- References -- Space-Efficient STR-IC-LCS Computation -- 1 Introduction -- 2 Preliminaries -- 2.1 Strings -- 2.2 STR-IC-LCS -- 3 Space-efficient Solution for STR-IC-LCS Problem -- 3.1 Overview of Our Solution -- 3.2 Space-efficient Prefix LCS -- 3.3 Algorithm -- 4 Conclusions and Future Work -- References -- The k-Centre Problem for Classes of Cyclic Words -- 1 Introduction -- 2 Preliminaries -- 3 The k-centre Problem for Necklaces -- 3.1 The Overlap Distance and the k-centre Problem -- 3.2 The k-centre Problem -- 4 Approximating the k-centre Problem for necklaces -- References -- Author Index. |
| Record Nr. | UNISA-996503468603316 |
| Cham, Switzerland : , : Springer, , [2023] | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
SOFSEM 2023, theory and practice of computer science : 48th international conference on current trends in theory and practice of computer science, SOFSEM 2023, Nový Smokovec, Slovakia, January 15-18, 2023, proceedings / / edited by Leszek Gąsieniec
| SOFSEM 2023, theory and practice of computer science : 48th international conference on current trends in theory and practice of computer science, SOFSEM 2023, Nový Smokovec, Slovakia, January 15-18, 2023, proceedings / / edited by Leszek Gąsieniec |
| Pubbl/distr/stampa | Cham, Switzerland : , : Springer, , [2023] |
| Descrizione fisica | 1 online resource (401 pages) |
| Disciplina | 004 |
| Collana | Lecture Notes in Computer Science |
| Soggetto topico | Computer science |
| ISBN |
9783031231018
9783031231001 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Intro -- Preface -- Organization -- Contents -- Graphs Problems and Optimisation -- The Complexity of Finding Tangles -- 1 Introduction -- 2 Exact Algorithms -- 3 Complexity -- 4 Counterexample to Conjecture 1 -- References -- A Spectral Algorithm for Finding Maximum Cliques in Dense Random Intersection Graphs -- 1 Introduction -- 1.1 Previous Work on Maximum Cliques in Random Intersection Graphs -- 2 Our Contribution -- 3 Definitions, Notation and Useful Results -- 3.1 Range of Values for m,n,p -- 4 The Spectral Algorithm -- 4.1 Running Time of Our Algorithm -- 5 Experimental Evaluation -- 6 Conclusions -- 7 Appendix -- 7.1 Greedy-Clique Algorithm -- 7.2 Mono-Clique Algorithm -- 7.3 Maximum-Clique Algorithm -- References -- Solving Cut-Problems in Quadratic Time for Graphs with Bounded Treewidth -- 1 Introduction -- 2 Related Work -- 3 Preliminaries -- 4 Max-Bisection: From O(2t n3) to O(2tn2) -- 5 Our Framework -- 6 Conclusion -- References -- More Effort Towards Multiagent Knapsack -- 1 Introduction -- 2 Hardness of Median-UK -- 3 Algorithms for Special Cases -- 3.1 When = 1: Diverse Knapsack -- 4 Conclusion -- References -- Graph Drawing and Visualization -- Dominance Drawings for DAGs with Bounded Modular Width -- 1 Introduction -- 2 Preliminaries -- 3 The Compaction Lemma -- 4 Minimizing the Number of Fips -- 5 Minimizing the Number of Dimensions -- 6 Concluding Remarks -- References -- Morphing Planar Graph Drawings Through 3D -- 1 Introduction -- 2 An Upper Bound -- 2.1 3D Morph Operations -- 2.2 3D Morphs for Biconnected Planar Graphs -- 2.3 3D Morphs for General Planar Graphs -- 3 Discussion: Lower Bounds -- 4 Open Problems -- References -- Visualizing Multispecies Coalescent Trees: Drawing Gene Trees Inside Species Trees -- 1 Introduction -- 2 Drawing Style -- 3 NP-Hardness -- 4 Planar Instances -- 5 Algorithms -- References.
Parameterized Approaches to Orthogonal Compaction -- 1 Introduction -- 2 Basic Definitions -- 3 Number of Kitty Corners: An FPT Algorithm -- 4 A Polynomial Kernel for Cycle Graphs -- 5 Maximum Face Degree: Parameterized Hardness -- 6 Height of the Representation: An XP Algorithm -- 7 Open Problems -- References -- NP-Hardness and Fixed Parameter Tractability -- Hardness of Bounding Influence via Graph Modification -- 1 Introduction -- 2 Related Work -- 3 Preliminaries -- 3.1 Graph Theoretic Terminology -- 3.2 Centrality Measures -- 4 Bounding the Influence of Vertex Centrality Scores -- References -- Heuristics for Opinion Diffusion via Local Elections -- 1 Introduction -- 1.1 Our Contributions -- 1.2 Related Work -- 2 Formal Model -- 2.1 Opinion Graphs -- 2.2 Campaigning and Bribery -- 2.3 Diffusion Processes via Local Elections -- 2.4 Election Results via Global Voting Rules -- 2.5 Optimization Goals -- 3 Computing Optimal Bribery Schemes -- 3.1 Heuristic Methods -- 4 Simulations -- 4.1 Experimental Design -- 4.2 Results -- 5 Outlook -- References -- On the Parameterized Complexity of s-club Cluster Deletion Problems -- 1 Introduction -- 2 Preliminaries -- 3 Algorithm for s-Club Cluster Edge Deletion -- 3.1 Definition of the Records -- 3.2 Description of the Algorithm -- 4 Algorithm for s-Club Cluster Vertex Deletion -- 5 Discussion and Open Problems -- References -- SOFSEM 2023 Best Papers -- Balanced Substructures in Bicolored Graphs -- 1 Introduction -- 2 NP-hardness Results -- 2.1 Complexity in Split Graphs -- 3 Small Balanced Paths, Trees and Connected Subgraphs -- 4 FPT Algorithms -- 4.1 Randomized Algorithms -- 4.2 Deterministic Algorithms -- 5 Concluding Remarks -- References -- On the Complexity of Scheduling Problems with a Fixed Number of Parallel Identical Machines -- 1 Introduction -- 2 Preliminaries -- 2.1 Subset Sum and Partition. 2.2 Scheduling -- 2.3 The Scheduling Lower Bounds by Abboud et al. -- 2.4 Our Results -- 3 Problems with One Machine -- 4 Problems with Multiple Machines -- 5 Conclusion -- References -- SOFSEM 2023 Best Student Papers -- On the 2-Layer Window Width Minimization Problem -- 1 Introduction -- 2 Window Width Minimization with Bottom Layer Fixed -- 3 Window Width Minimization with Top Layer Fixed -- 4 Open Problems -- References -- Sequentially Swapping Tokens: Further on Graph Classes -- 1 Introduction -- 2 Preliminaries -- 3 Polynomial-Time Algorithm for Block-Cactus Graphs -- 3.1 Reduction to a Generalized Problem on Biconnected Components -- 3.2 Sub-STS on cycles -- 3.3 Sub-STS on complete graphs -- 3.4 The Whole Algorithm -- 4 Hardness of the Few-Color and Colorful Cases -- 4.1 General Tools for Showing Hardness -- 4.2 The Few-Color Case on Grid-Like Graphs -- 4.3 The Colorful Case on Grid-Like Graphs -- 5 Concluding Remarks -- References -- Communication and Temporal Graphs -- On the Preservation of Properties When Changing Communication Models -- 1 Introduction -- 2 The FIFO System -- 3 Comparing Channel Layouts -- 4 Property Preservation -- 4.1 Reachability -- 4.2 Deadlock Freedom -- 4.3 Confluence -- 4.4 Summary of Results -- 5 Conclusion -- References -- Introduction to Routing Problems with Mandatory Transitions -- 1 Introduction -- 2 Shortest Path Problems with Mandatory Transitions -- 2.1 Polynomiality of SPMT -- 2.2 Non Approximation of Elementary SPMTand MRMT -- 3 Routing Problems with Mandatory Transitions -- 4 Conclusion -- References -- Payment Scheduling in the Interval Debt Model -- 1 Introduction -- 2 The Interval Debt Model -- 2.1 Formal Setting -- 2.2 Schedules -- 2.3 Problem Definitions -- 3 Our Results -- 3.1 Hardness Results -- 3.2 Polynomial-Time Algorithms -- 4 Conclusion and Open Problems -- References. Multi-Parameter Analysis of Finding Minors and Subgraphs in Edge-Periodic Temporal Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Temporal Extension of Graph Problems -- 4 Periodic Character Alignment -- 5 Minors and Subgraphs -- 5.1 Subgraphs -- 5.2 Minors -- 5.3 Further Parameterized Analysis -- 6 Short Traversal -- 7 Conclusion -- References -- Complexity and Learning -- Lower Bounds for Monotone q-Multilinear Boolean Circuits -- 1 Introduction -- 2 Monotone Boolean Circuits and Functions -- 3 Monotone q-multilinear Boolean Circuits -- 3.1 q-multilinearity Versus Bounded Conjunction Depth -- 4 Lower Bounds for q-multilinear Boolean Circuits -- 4.1 Lower Bound Trade-Offs for Semi-disjoint Bilinear Forms -- 4.2 Lower Bounds for Isolk,n -- References -- A Faster Algorithm for Determining the Linear Feasibility of Systems of BTVPI Constraints -- 1 Introduction -- 2 Statement of Problems -- 3 A Rewrite Version of Fourier-Motzkin Elimination -- 4 The BCS Linear Programming Algorithm -- 4.1 Analysis -- 5 Conclusion -- References -- Quantum Complexity for Vector Domination Problem -- 1 Introduction -- 1.1 Prior Work -- 1.2 Our Results -- 2 Preliminaries -- 2.1 Problem Definitions -- 2.2 Quantum Query Model -- 2.3 Techniques -- 3 Vector Domination -- 3.1 Lower Bounds -- 3.2 Upper Bounds -- 4 Minimum Inner Product -- 4.1 Idea -- 4.2 Preprocessing -- 4.3 Reduction -- 5 Open Questions -- References -- Learning Through Imitation by Using Formal Verification -- 1 Introduction -- 2 Related Work -- 3 Method -- 3.1 Q-Learning -- 3.2 Using a Model Checker on the Q-learning Model -- 4 Model Checker as an Expert-Applications -- 4.1 Convergence with Fewer Epochs -- 4.2 Help Convergence by Avoiding Sub-optimal Solutions -- 4.3 Explore Unseen States -- 5 Discussion -- References -- Robots and Strings -- Delivery to Safety with Two Cooperating Robots -- 1 Introduction. 1.1 Model, Notation, and Preliminaries -- 1.2 Related Work -- 1.3 Outline and Results of the Paper -- 2 Optimal Offline Algorithm -- 3 Online Algorithm for the OneAxis Model -- 4 Online Algorithms for the NoAxis Model -- 4.1 VisibleBoundary Model -- 4.2 DiscoverableBoundary Model -- 4.3 InvisibleBoundary Model -- 5 Conclusion -- References -- Space-Efficient STR-IC-LCS Computation -- 1 Introduction -- 2 Preliminaries -- 2.1 Strings -- 2.2 STR-IC-LCS -- 3 Space-efficient Solution for STR-IC-LCS Problem -- 3.1 Overview of Our Solution -- 3.2 Space-efficient Prefix LCS -- 3.3 Algorithm -- 4 Conclusions and Future Work -- References -- The k-Centre Problem for Classes of Cyclic Words -- 1 Introduction -- 2 Preliminaries -- 3 The k-centre Problem for Necklaces -- 3.1 The Overlap Distance and the k-centre Problem -- 3.2 The k-centre Problem -- 4 Approximating the k-centre Problem for necklaces -- References -- Author Index. |
| Record Nr. | UNINA-9910635400403321 |
| Cham, Switzerland : , : Springer, , [2023] | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||