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.
Advanced Mathematical Science for Mobility Society / / edited by Kazushi Ikeda, Yoshiumi Kawamura, Kazuhisa Makino, Satoshi Tsujimoto, Nobuo Yamashita, Shintaro Yoshizawa, Hanna Sumita
| Advanced Mathematical Science for Mobility Society / / edited by Kazushi Ikeda, Yoshiumi Kawamura, Kazuhisa Makino, Satoshi Tsujimoto, Nobuo Yamashita, Shintaro Yoshizawa, Hanna Sumita |
| Edizione | [1st ed. 2024.] |
| Pubbl/distr/stampa | Singapore : , : Springer Nature Singapore : , : Imprint : Springer, , 2024 |
| Descrizione fisica | 1 online resource (VIII, 215 p. 52 illus., 40 illus. in color.) |
| Disciplina | 004.0151 |
| Soggetto topico |
Computer science
Mathematical models Quantitative research Transportation engineering Traffic engineering Theory and Algorithms for Application Domains Mathematical Modeling and Industrial Mathematics Data Analysis and Big Data Transportation Technology and Traffic Engineering |
| ISBN | 981-9997-72-0 |
| Formato | Materiale a stampa  |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Part 1. Introduction, motivation, and direction for Advanced Mathematical Science for Mobility Society, together with the project between Toyota Motor Corporation and Kyoto University -- Chapter 1. Advanced Mathematical Science for Mobility Society -- Part 2. Mathematical models of flow Chapter. 2. Analysis of many-body particle systems by geometry and box-ball-system theory -- Chapter 3. Discrete Integrable Systems, LR transformations and Box-Ball Systems -- Part 3. Mathematical methods for huge data and network analysis -- Chapter 4. Eigenvalue Analysis in Mobility Data -- Chapter 5. Application of tensor network formalism for processing tensor data -- Chapter 6. Machine Learning Approach to Mobility Analysis -- Chapter 7. Graph optimization problems and algorithms for DAG-type blockchains -- Part 4. Algorithm for mobility society -- Chapter 8. Control and optimization of one-way car-sharing systems -- Chapter 9. Algorithms for future mobility society Chapter 10. Mechanism Design for Mobility. |
| Record Nr. | UNINA-9910845080703321 |
| Singapore : , : Springer Nature Singapore : , : Imprint : Springer, , 2024 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Algorithms and Computation [[electronic resource] ] : 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings / / edited by Khaled Elbassioni, Kazuhisa Makino
| Algorithms and Computation [[electronic resource] ] : 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings / / edited by Khaled Elbassioni, Kazuhisa Makino |
| Edizione | [1st ed. 2015.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2015 |
| Descrizione fisica | 1 online resource (XXII, 793 p. 131 illus.) |
| Disciplina | 005.1 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Algorithms
Computer science—Mathematics Discrete mathematics Computer graphics Artificial intelligence—Data processing Numerical analysis Discrete Mathematics in Computer Science Computer Graphics Data Science Numerical Analysis |
| ISBN | 3-662-48971-6 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Intro -- Preface -- Organization -- Invited Talks -- Soft Clustering: Models and Algorithms -- Computing on Strategic Inputs -- Lower Bounds on the Size of Linear Programs -- Contents -- Computational Geometry I -- An Optimal Algorithm for Tiling the Plane with a Translated Polyomino -- 1 Introduction -- 2 Definitions -- 2.1 Words -- 2.2 Factors -- 2.3 Special Words and Factors -- 2.4 Polyominoes and Boundary Words -- 2.5 Tilings -- 3 The Beauquier-Nivat Criterion -- 4 A Bound on the Number of Factorizations -- 5 An Algorithm for Enumerating Factorizations -- References -- Adaptive Point Location in Planar Convex Subdivisions -- 1 Introduction -- 2 Triangulation of a Convex Polygon -- 3 Point Location in a Convex Subdivision -- 4 Conclusion -- References -- Competitive Local Routing with Constraints -- 1 Introduction -- 2 Preliminaries -- 3 Lower Bound on Local Routing -- 4 Routing on the Constrained 6-Graph -- 4.1 Positive Routing on the Constrained Half-6-Graph -- 4.2 Routing on the Constrained 6-Graph -- 4.3 Negative Routing on the Constrained Half-6-Graph -- References -- Navigating Weighted Regions with Scattered Skinny Tetrahedra -- 1 Introduction -- 2 Preliminaries -- 3 Placement of Steiner Points -- 4 Steiner Graph and Snapping -- 5 Processing Extended Clusters and Vertex Stars -- 5.1 Locally Shortest Path -- 5.2 Approximate Shortest Path -- References -- Data Structures -- On the Succinct Representation of Unlabeled Permutations -- 1 Introduction and Motivation -- 2 Definitions and Preliminaries -- 3 Direct Labeling Scheme -- 4 Succinct Data Structures with Label Space n -- 5 Succinct Data Structures with Label Space cn1+ -- 6 Lower Bounds -- 6.1 Lower Bound for Auxiliary Data with Label Space cn -- 6.2 Lower Bound for Auxiliary Data with Label Space cn1+ -- 7 Applications -- 8 Conclusion -- References.
How to Select the Top k Elements from Evolving Data? -- 1 Introduction -- 2 Preliminaries -- 3 Consecutive-Swapping Model -- 3.1 An Algorithm for the Top-k-set Problem -- 3.2 An Algorithm for the Top-k-selection Problem -- 3.3 Lower Bounds for the Top-k-selection Problem -- 4 Gaussian-Swapping Model -- 5 Conclusions -- References -- Optimal Search Trees with 2-Way Comparisons -- 1 Background and Statement of Results -- 2 Proof of Spuler's Conjecture -- 3 Proofs of Theorem1 (Algorithm for 2wcst) and Theorem3 -- 3.1 Perturbation Argument -- Proofs of Theorems1 and 3 -- 4 Proof of Theorem2 (Additive-3 Approximation Algorithm) -- 5 Proof of Theorem4 (Errors in Work on Binary Split Trees) -- 6 Proof of Theorem5 (O(nlogn) Time Without Equality) -- 7 Appendix -- 7.1 Python Code for Theorem4 (gbst Algorithm of [9]) -- References -- Multidimensional Range Selection -- 1 Introduction -- 2 Preliminaries -- 3 The ``Abstract'' Problem -- 4 Range Selection -- 5 Dominance Counting and Parallel Counting -- References -- Combinatorial Optimization and Approximation Algorithms I -- On the Minimum Cost Range Assignment Problem -- 1 Introduction -- 2 Minimum Cost Range Assignment in 1D -- 2.1 An Exact Algorithm for the 1D MinRange Problem -- 2.2 An Exact Algorithm for the 1D MinRangeSpanner Problem -- 3 The MinRange Problem in Higher Dimensions -- 3.1 Our Approach -- 3.2 The Approximation Algorithm -- References -- On the Approximability of the Minimum Rainbow Subgraph Problem and Other Related Problems -- 1 Introduction -- 2 An O(n1/3) Approximation Algorithm for DkCS -- 2.1 Preliminaries -- 2.2 Procedure A1: A Trivial Procedure -- 2.3 Procedure A2: A Greedy Procedure -- 2.4 Colored Walks of Length 2 -- 2.5 Procedure A4: Another Greedy Procedure -- 2.6 Algorithm A -- 2.7 An Algorithm for MIN-REP -- 3 Reduction from the Densest k-Subgraph (DkS) Problem -- References. General Caching Is Hard: Even with Small Pages -- 1 Introduction -- 2 Reduction -- 3 Proof of Correctness -- References -- Randomized Algorithms I -- The Secretary Problem with a Choice Function -- 1 Introduction -- 2 Model -- 3 Algorithm -- 4 Upper Bounds -- References -- The Benefit of Recombination in Noisy Evolutionary Search -- 1 Introduction -- 2 Preliminaries -- 2.1 Algorithms -- 3 Results -- 3.1 Mutation-Based Approach -- 3.2 Compact GA -- 4 Conclusions -- References -- Algorithmic Learning for Steganography: Proper Learning of k-term DNF Formulas from Positive Samples -- 1 Introduction -- 2 Preliminaries -- 3 Learning k-term DNF from Positive Samples -- 4 Learning Documents for Steganography -- 5 Conclusions -- References -- Combinatorial Optimization and Approximation Algorithms II -- Obtaining a Triangular Matrix by Independent Row-Column Permutations -- 1 Introduction -- 2 Notations -- 3 Answering Wilf's Question -- 3.1 Disproving a Previous Related Result -- 3.2 Our NP-completeness Proof for Wilf's Question -- 4 Exponential-Time Algorithm -- 5 Conclusion -- References -- Many-to-one Matchings with Lower Quotas: Algorithms and Complexity -- 1 Introduction -- 2 Degree- and Quota-restricted Cases -- 2.1 Problem Definition -- 2.2 Degree-Restricted Cases -- 2.3 Quota-Restricted Cases -- 3 Bounded treewidth graphs -- 4 Approximation -- References -- Minimizing the Maximum Moving Cost of Interval Coverage -- 1 Introduction -- 2 Preliminaries -- 3 The Decision Problem -- 3.1 The Algorithm Description -- 3.2 The Algorithm Implementation -- 4 The Optimization Problem -- 4.1 An Overview -- 4.2 A General i-th Step -- 4.3 Maintaining the Algorithm Invariants -- References -- Randomized Algorithms II -- Heuristic Time Hierarchies via Hierarchies for Sampling Distributions -- 1 Introduction -- 2 Preliminaries -- 3 Hierarchy for. 4 Conditional Hierarchy -- 5 Hierarchy for k-valued Functions -- 6 Hierarchy for Arbitrary Distributions -- 7 Hierarchy for -- References -- Unbounded Discrepancy of Deterministic Random Walks on Grids -- 1 Introduction -- 2 Preliminaries -- 3 Stable Configuration of the Rotor-Router Model -- 4 Conclusion -- References -- Trading off Worst and Expected Cost in Decision Tree Problems -- 1 Introduction -- 2 Trade-off: Upper Bound -- 3 Trade-off: Lower Bound -- 3.1 The Structure of the Instance I in Theorem ?? -- 3.2 Proof of Theorem ?? -- 4 Open Problems -- References -- Graph Algorithms and FPT I -- Sliding Token on Bipartite Permutation Graphs -- 1 Introduction -- 1.1 Preliminaries -- 2 Coping with Rigid Tokens -- 3 An Algorithm on Bipartite Graphs -- 4 Sliding Token on Bipartite Permutation Graphs -- 5 Sliding Token on Bipartite Distance-Hereditary Graphs -- 6 Discussion -- References -- Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width -- 1 Introduction -- 2 Definitions and Preliminaries -- 3 Enumerations for Graphs of Bounded LMIM-width -- 4 Enumeration of Minimal Dominating Sets for Unit Square Graphs -- References -- Minimum Degree Up to Local Complementation: Bounds, Parameterized Complexity, and Exact Algorithms -- 1 Introduction -- 2 Upperbounds on the Local Minimum Degree -- 3 Parameterized Complexity -- 4 Exponential Algorithms -- 5 Conclusion -- References -- Exact and FPT Algorithms for Max-Conflict Free Coloring in Hypergraphs -- 1 Introduction -- 2 Preliminaries -- 3 FPT Algorithm for p-CFC -- 4 Exact Algorithm for Max-Conflict Free Coloring -- References -- Computational Geometry II -- Geometric Matching Algorithms for Two Realistic Terrains -- 1 Introduction -- 1.1 Our Results -- 2 Translation Space Under L Metric -- 2.1 Candidate Pairs Defining the Distance Between Two Terrains. 2.2 Subdividing Translation Space -- 2.3 Complexity of the Subdivision M -- 3 Geometric Matching Algorithms Under L Metric -- 3.1 Construction of M -- 3.2 A Deterministic Geometric Matching Algorithm -- 3.3 A Randomized Geometric Matching Algorithm -- 4 Geometric Matching Algorithm Under L1 Metric -- References -- Size-Dependent Tile Self-Assembly: Constant-Height Rectangles and Stability -- 1 Introduction -- 2 Definitions -- 2.1 Tiles, Assemblies, and Supertiles -- 2.2 The Assembly Process -- 2.3 Two-Handed Tile Assembly Systems -- 2.4 Size-Dependent Systems -- 3 Constant-Height Rectangles -- 4 Squares -- 5 -stabilility is coNP-complete -- 6 Open Problems -- References -- The 2-Center Problem in a Simple Polygon -- 1 Introduction -- 2 Preliminary -- 3 The Partition by an Optimal 2-center -- 3.1 Computing a Set of Candidate Edge Pairs -- 4 A Decision Algorithm for a Candidate Edge Pair -- 4.1 Computing the Intersection of Geodesic Disks -- 4.2 Subdividing the Edges and the Chains -- 4.3 Four Coverage Functions and Their Extrema -- 4.4 Computing a 2-center for a Pair of Subchains -- 4.5 The Analysis of the Decision Algorithm -- 5 An Optimization Algorithm for a Candidate Edge Pair -- 5.1 Computing the Coverage Function Values -- 5.2 Constructing 4-Tuples Consisting of Two Cells and Two Subedges -- References -- Choice Is Hard -- 1 Introduction -- 2 A New Satisfiability Result -- 3 Applications of LSAT to Rainbow Problems -- 3.1 Rainbow Minmax Gap (Decision Version) is NP-complete -- 3.2 Rainbow Piercing and Rainbow Covering are NP-complete -- 4 Exact Coverage of Color Classes -- 4.1 Unit Intervals -- 4.2 Arbitrary Length Intervals -- References -- Graph Algorithms and FPT II -- Fully Dynamic Betweenness Centrality -- 1 Introduction -- 2 The Fully Dynamic Betweenness Centrality Algorithm -- 3 Background -- 3.1 The NPR Decremental APASP Algorithm [19]. 3.2 The DI Fully Dynamic APSP Algorithm [8]. |
| Record Nr. | UNISA-996466188303316 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2015 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Algorithms and Computation : 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings / / edited by Khaled Elbassioni, Kazuhisa Makino
| Algorithms and Computation : 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings / / edited by Khaled Elbassioni, Kazuhisa Makino |
| Edizione | [1st ed. 2015.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2015 |
| Descrizione fisica | 1 online resource (XXII, 793 p. 131 illus.) |
| Disciplina | 005.1 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Algorithms
Computer science—Mathematics Discrete mathematics Computer graphics Artificial intelligence—Data processing Numerical analysis Discrete Mathematics in Computer Science Computer Graphics Data Science Numerical Analysis |
| ISBN | 3-662-48971-6 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Intro -- Preface -- Organization -- Invited Talks -- Soft Clustering: Models and Algorithms -- Computing on Strategic Inputs -- Lower Bounds on the Size of Linear Programs -- Contents -- Computational Geometry I -- An Optimal Algorithm for Tiling the Plane with a Translated Polyomino -- 1 Introduction -- 2 Definitions -- 2.1 Words -- 2.2 Factors -- 2.3 Special Words and Factors -- 2.4 Polyominoes and Boundary Words -- 2.5 Tilings -- 3 The Beauquier-Nivat Criterion -- 4 A Bound on the Number of Factorizations -- 5 An Algorithm for Enumerating Factorizations -- References -- Adaptive Point Location in Planar Convex Subdivisions -- 1 Introduction -- 2 Triangulation of a Convex Polygon -- 3 Point Location in a Convex Subdivision -- 4 Conclusion -- References -- Competitive Local Routing with Constraints -- 1 Introduction -- 2 Preliminaries -- 3 Lower Bound on Local Routing -- 4 Routing on the Constrained 6-Graph -- 4.1 Positive Routing on the Constrained Half-6-Graph -- 4.2 Routing on the Constrained 6-Graph -- 4.3 Negative Routing on the Constrained Half-6-Graph -- References -- Navigating Weighted Regions with Scattered Skinny Tetrahedra -- 1 Introduction -- 2 Preliminaries -- 3 Placement of Steiner Points -- 4 Steiner Graph and Snapping -- 5 Processing Extended Clusters and Vertex Stars -- 5.1 Locally Shortest Path -- 5.2 Approximate Shortest Path -- References -- Data Structures -- On the Succinct Representation of Unlabeled Permutations -- 1 Introduction and Motivation -- 2 Definitions and Preliminaries -- 3 Direct Labeling Scheme -- 4 Succinct Data Structures with Label Space n -- 5 Succinct Data Structures with Label Space cn1+ -- 6 Lower Bounds -- 6.1 Lower Bound for Auxiliary Data with Label Space cn -- 6.2 Lower Bound for Auxiliary Data with Label Space cn1+ -- 7 Applications -- 8 Conclusion -- References.
How to Select the Top k Elements from Evolving Data? -- 1 Introduction -- 2 Preliminaries -- 3 Consecutive-Swapping Model -- 3.1 An Algorithm for the Top-k-set Problem -- 3.2 An Algorithm for the Top-k-selection Problem -- 3.3 Lower Bounds for the Top-k-selection Problem -- 4 Gaussian-Swapping Model -- 5 Conclusions -- References -- Optimal Search Trees with 2-Way Comparisons -- 1 Background and Statement of Results -- 2 Proof of Spuler's Conjecture -- 3 Proofs of Theorem1 (Algorithm for 2wcst) and Theorem3 -- 3.1 Perturbation Argument -- Proofs of Theorems1 and 3 -- 4 Proof of Theorem2 (Additive-3 Approximation Algorithm) -- 5 Proof of Theorem4 (Errors in Work on Binary Split Trees) -- 6 Proof of Theorem5 (O(nlogn) Time Without Equality) -- 7 Appendix -- 7.1 Python Code for Theorem4 (gbst Algorithm of [9]) -- References -- Multidimensional Range Selection -- 1 Introduction -- 2 Preliminaries -- 3 The ``Abstract'' Problem -- 4 Range Selection -- 5 Dominance Counting and Parallel Counting -- References -- Combinatorial Optimization and Approximation Algorithms I -- On the Minimum Cost Range Assignment Problem -- 1 Introduction -- 2 Minimum Cost Range Assignment in 1D -- 2.1 An Exact Algorithm for the 1D MinRange Problem -- 2.2 An Exact Algorithm for the 1D MinRangeSpanner Problem -- 3 The MinRange Problem in Higher Dimensions -- 3.1 Our Approach -- 3.2 The Approximation Algorithm -- References -- On the Approximability of the Minimum Rainbow Subgraph Problem and Other Related Problems -- 1 Introduction -- 2 An O(n1/3) Approximation Algorithm for DkCS -- 2.1 Preliminaries -- 2.2 Procedure A1: A Trivial Procedure -- 2.3 Procedure A2: A Greedy Procedure -- 2.4 Colored Walks of Length 2 -- 2.5 Procedure A4: Another Greedy Procedure -- 2.6 Algorithm A -- 2.7 An Algorithm for MIN-REP -- 3 Reduction from the Densest k-Subgraph (DkS) Problem -- References. General Caching Is Hard: Even with Small Pages -- 1 Introduction -- 2 Reduction -- 3 Proof of Correctness -- References -- Randomized Algorithms I -- The Secretary Problem with a Choice Function -- 1 Introduction -- 2 Model -- 3 Algorithm -- 4 Upper Bounds -- References -- The Benefit of Recombination in Noisy Evolutionary Search -- 1 Introduction -- 2 Preliminaries -- 2.1 Algorithms -- 3 Results -- 3.1 Mutation-Based Approach -- 3.2 Compact GA -- 4 Conclusions -- References -- Algorithmic Learning for Steganography: Proper Learning of k-term DNF Formulas from Positive Samples -- 1 Introduction -- 2 Preliminaries -- 3 Learning k-term DNF from Positive Samples -- 4 Learning Documents for Steganography -- 5 Conclusions -- References -- Combinatorial Optimization and Approximation Algorithms II -- Obtaining a Triangular Matrix by Independent Row-Column Permutations -- 1 Introduction -- 2 Notations -- 3 Answering Wilf's Question -- 3.1 Disproving a Previous Related Result -- 3.2 Our NP-completeness Proof for Wilf's Question -- 4 Exponential-Time Algorithm -- 5 Conclusion -- References -- Many-to-one Matchings with Lower Quotas: Algorithms and Complexity -- 1 Introduction -- 2 Degree- and Quota-restricted Cases -- 2.1 Problem Definition -- 2.2 Degree-Restricted Cases -- 2.3 Quota-Restricted Cases -- 3 Bounded treewidth graphs -- 4 Approximation -- References -- Minimizing the Maximum Moving Cost of Interval Coverage -- 1 Introduction -- 2 Preliminaries -- 3 The Decision Problem -- 3.1 The Algorithm Description -- 3.2 The Algorithm Implementation -- 4 The Optimization Problem -- 4.1 An Overview -- 4.2 A General i-th Step -- 4.3 Maintaining the Algorithm Invariants -- References -- Randomized Algorithms II -- Heuristic Time Hierarchies via Hierarchies for Sampling Distributions -- 1 Introduction -- 2 Preliminaries -- 3 Hierarchy for. 4 Conditional Hierarchy -- 5 Hierarchy for k-valued Functions -- 6 Hierarchy for Arbitrary Distributions -- 7 Hierarchy for -- References -- Unbounded Discrepancy of Deterministic Random Walks on Grids -- 1 Introduction -- 2 Preliminaries -- 3 Stable Configuration of the Rotor-Router Model -- 4 Conclusion -- References -- Trading off Worst and Expected Cost in Decision Tree Problems -- 1 Introduction -- 2 Trade-off: Upper Bound -- 3 Trade-off: Lower Bound -- 3.1 The Structure of the Instance I in Theorem ?? -- 3.2 Proof of Theorem ?? -- 4 Open Problems -- References -- Graph Algorithms and FPT I -- Sliding Token on Bipartite Permutation Graphs -- 1 Introduction -- 1.1 Preliminaries -- 2 Coping with Rigid Tokens -- 3 An Algorithm on Bipartite Graphs -- 4 Sliding Token on Bipartite Permutation Graphs -- 5 Sliding Token on Bipartite Distance-Hereditary Graphs -- 6 Discussion -- References -- Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width -- 1 Introduction -- 2 Definitions and Preliminaries -- 3 Enumerations for Graphs of Bounded LMIM-width -- 4 Enumeration of Minimal Dominating Sets for Unit Square Graphs -- References -- Minimum Degree Up to Local Complementation: Bounds, Parameterized Complexity, and Exact Algorithms -- 1 Introduction -- 2 Upperbounds on the Local Minimum Degree -- 3 Parameterized Complexity -- 4 Exponential Algorithms -- 5 Conclusion -- References -- Exact and FPT Algorithms for Max-Conflict Free Coloring in Hypergraphs -- 1 Introduction -- 2 Preliminaries -- 3 FPT Algorithm for p-CFC -- 4 Exact Algorithm for Max-Conflict Free Coloring -- References -- Computational Geometry II -- Geometric Matching Algorithms for Two Realistic Terrains -- 1 Introduction -- 1.1 Our Results -- 2 Translation Space Under L Metric -- 2.1 Candidate Pairs Defining the Distance Between Two Terrains. 2.2 Subdividing Translation Space -- 2.3 Complexity of the Subdivision M -- 3 Geometric Matching Algorithms Under L Metric -- 3.1 Construction of M -- 3.2 A Deterministic Geometric Matching Algorithm -- 3.3 A Randomized Geometric Matching Algorithm -- 4 Geometric Matching Algorithm Under L1 Metric -- References -- Size-Dependent Tile Self-Assembly: Constant-Height Rectangles and Stability -- 1 Introduction -- 2 Definitions -- 2.1 Tiles, Assemblies, and Supertiles -- 2.2 The Assembly Process -- 2.3 Two-Handed Tile Assembly Systems -- 2.4 Size-Dependent Systems -- 3 Constant-Height Rectangles -- 4 Squares -- 5 -stabilility is coNP-complete -- 6 Open Problems -- References -- The 2-Center Problem in a Simple Polygon -- 1 Introduction -- 2 Preliminary -- 3 The Partition by an Optimal 2-center -- 3.1 Computing a Set of Candidate Edge Pairs -- 4 A Decision Algorithm for a Candidate Edge Pair -- 4.1 Computing the Intersection of Geodesic Disks -- 4.2 Subdividing the Edges and the Chains -- 4.3 Four Coverage Functions and Their Extrema -- 4.4 Computing a 2-center for a Pair of Subchains -- 4.5 The Analysis of the Decision Algorithm -- 5 An Optimization Algorithm for a Candidate Edge Pair -- 5.1 Computing the Coverage Function Values -- 5.2 Constructing 4-Tuples Consisting of Two Cells and Two Subedges -- References -- Choice Is Hard -- 1 Introduction -- 2 A New Satisfiability Result -- 3 Applications of LSAT to Rainbow Problems -- 3.1 Rainbow Minmax Gap (Decision Version) is NP-complete -- 3.2 Rainbow Piercing and Rainbow Covering are NP-complete -- 4 Exact Coverage of Color Classes -- 4.1 Unit Intervals -- 4.2 Arbitrary Length Intervals -- References -- Graph Algorithms and FPT II -- Fully Dynamic Betweenness Centrality -- 1 Introduction -- 2 The Fully Dynamic Betweenness Centrality Algorithm -- 3 Background -- 3.1 The NPR Decremental APASP Algorithm [19]. 3.2 The DI Fully Dynamic APSP Algorithm [8]. |
| Record Nr. | UNINA-9910484799203321 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2015 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||