top

  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.

  Info

  • Utilizzare questo link per rimuovere la selezione effettuata.

Biblioteca

MARC Lista (tabellare)
Algorithms and Complexity [[electronic resource] ] : 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings / / edited by Vangelis Th. Paschos, Peter Widmayer
Algorithms and Complexity [[electronic resource] ] : 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings / / edited by Vangelis Th. Paschos, Peter Widmayer
Edizione [1st ed. 2015.]
Pubbl/distr/stampa Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015
Descrizione fisica 1 online resource (XV, 430 p. 81 illus.)
Disciplina 005.1
Collana Theoretical Computer Science and General Issues
Soggetto topico Algorithms
Computer science—Mathematics
Discrete mathematics
Artificial intelligence—Data processing
Discrete Mathematics in Computer Science
Data Science
ISBN 3-319-18173-4
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Communication, Dynamics and Renormalization -- Fast and Powerful Hashing using Tabulation -- Green Barrier Coverage with Mobile Sensors -- A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths -- Orthogonal Graph Drawing with Inflexible Edges -- Linear time Constructions of some d-Restriction Problems -- Efficiently Testing T-Interval Connectivity in Dynamic Graphs -- Competitive Strategies for Online Clique Clustering -- Scheduling with Gaps: New Models and Algorithms -- MinMax-Distance Gathering on given Meeting Points -- Evacuating Robots from a Disk Using Face-to-Face Communication -- Planarity of Streamed Graphs -- Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs -- Randomized Adaptive Test Cover -- Contraction Blockers for Graphs with Forbidden Induced Paths -- Label Placement in Road Maps -- Discrete Stochastic Submodular Maximization: Adaptive vs. Non-Adaptive vs. Offline -- Parameterized Algorithms and Kernels for 3-Hitting Set with Parity Constraints -- Simple strategies versus optimal schedules in multi-agent patrolling -- Sharing Non-Anonymous Costs of Multiple Resources Optimally -- Algorithms solving the Matching Cut problem -- End-Vertices of Graph Search Algorithms -- Deciding the On-line Chromatic Number of a Graph with Pre-coloring is PSPACE-complete -- A Lex-BFS-based recognition algorithm for Robinsonian matrices -- Mixed Map Labeling -- Optimal Online Edge Coloring of Planar Graphs with Advice -- Approximability of Two Variants of Multiple Knapsack -- Block Sorting is Hard -- An opportunistic text indexing structure based on run length encoding -- PSPACE-completeness of Bloxorz and of Games with 2-Buttons -- Advice Complexity of Fine-Grained Job Shop Scheduling.
Record Nr. UNINA-9910483445903321
Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui
Algorithms and Complexity [[electronic resource] ] : 8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013. Proceedings / / edited by Paul G. Spirakis, Maria Serna
Algorithms and Complexity [[electronic resource] ] : 8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013. Proceedings / / edited by Paul G. Spirakis, Maria Serna
Edizione [1st ed. 2013.]
Pubbl/distr/stampa Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013
Descrizione fisica 1 online resource (XIV, 384 p. 75 illus.)
Disciplina 006.31
Collana Theoretical Computer Science and General Issues
Soggetto topico Algorithms
Computer science—Mathematics
Discrete mathematics
Artificial intelligence—Data processing
Numerical analysis
Computer graphics
Computer networks
Discrete Mathematics in Computer Science
Data Science
Numerical Analysis
Computer Graphics
Computer Communication Networks
ISBN 3-642-38233-9
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Computational complexity and the use -- Design, analysis and experimentation -- Efficient algorithms -- Data structures.
Record Nr. UNISA-996466299903316
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013
Materiale a stampa
Lo trovi qui: Univ. di Salerno
Opac: Controlla la disponibilità qui
Algorithms and Complexity [[electronic resource] ] : 8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013. Proceedings / / edited by Paul G. Spirakis, Maria Serna
Algorithms and Complexity [[electronic resource] ] : 8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013. Proceedings / / edited by Paul G. Spirakis, Maria Serna
Edizione [1st ed. 2013.]
Pubbl/distr/stampa Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013
Descrizione fisica 1 online resource (XIV, 384 p. 75 illus.)
Disciplina 006.31
Collana Theoretical Computer Science and General Issues
Soggetto topico Algorithms
Computer science—Mathematics
Discrete mathematics
Artificial intelligence—Data processing
Numerical analysis
Computer graphics
Computer networks
Discrete Mathematics in Computer Science
Data Science
Numerical Analysis
Computer Graphics
Computer Communication Networks
ISBN 3-642-38233-9
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Computational complexity and the use -- Design, analysis and experimentation -- Efficient algorithms -- Data structures.
Record Nr. UNINA-9910484943003321
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui
Algorithms and Complexity [[electronic resource] ] : 7th International Conference, CIAC 2010, Rome, Italy, May 26-28, 2010, Proceedings / / edited by Josep Diaz, Tiziana Calamoneri
Algorithms and Complexity [[electronic resource] ] : 7th International Conference, CIAC 2010, Rome, Italy, May 26-28, 2010, Proceedings / / edited by Josep Diaz, Tiziana Calamoneri
Edizione [1st ed. 2010.]
Pubbl/distr/stampa Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2010
Descrizione fisica 1 online resource (XI, 384 p.)
Disciplina 004.0151
Collana Theoretical Computer Science and General Issues
Soggetto topico Computer programming
Computer networks
Computer science
Algorithms
Computer science—Mathematics
Discrete mathematics
Artificial intelligence—Data processing
Programming Techniques
Computer Communication Networks
Theory of Computation
Discrete Mathematics in Computer Science
Data Science
ISBN 1-280-38657-6
9786613564498
3-642-13073-9
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Invited Talks -- Towards a Distributed Search Engine -- Mechanisms for the Marriage and the Assignment Game -- Resilient Algorithms and Data Structures -- Session 1. Graph Algorithms I -- An Exact Algorithm for Connected Red-Blue Dominating Set -- Maximizing PageRank with New Backlinks -- Enumerating Rooted Graphs with Reflectional Block Structures -- Improved Approximations for TSP with Simple Precedence Constraints -- Polynomial Space Algorithms for Counting Dominating Sets and the Domatic Number -- Session 2. Computational Complexity -- Parameterized Complexity of Even/Odd Subgraph Problems -- Popular Matchings in the Marriage and Roommates Problems -- Bounding the Number of Tolerable Faults in Majority-Based Systems -- A Parameterized Algorithm for Chordal Sandwich -- Testing Computability by Width-2 OBDDs Where the Variable Order is Unknown -- Session 3. Graph Coloring -- Graph Unique-Maximum and Conflict-Free Colorings -- Strategic Coloring of a Graph -- Session 4. Tree Algorithms and Tree Decompositions -- Multicut Algorithms via Tree Decompositions -- The Steiner Tree Reoptimization Problem with Sharpened Triangle Inequality -- Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights -- A Planar Linear Arboricity Conjecture -- Session 5. Computational Geometry -- On the Number of Higher Order Delaunay Triangulations -- How Simple Robots Benefit from Looking Back -- Session 6. Game Theory -- On Strategy Improvement Algorithms for Simple Stochastic Games -- Online Cooperative Cost Sharing -- Session 7. Graph Algorithms II -- On the Power of Nodes of Degree Four in the Local Max-Cut Problem -- Packing Bipartite Graphs with Covers of Complete Bipartite Graphs -- Irredundant Set Faster Than O(2 n ) -- The Complexity of Computing Minimal Unidirectional Covering Sets -- A Parameterized Route to Exact Puzzles: Breaking the 2 n -Barrier for Irredundance -- Session 8. String Algorithms -- Finding the Maximum Suffix with Fewer Comparisons -- An Algorithmic Framework for Motif Discovery Problems in Weighted Sequences -- Session 9. Network Algorithms -- Capacitated Confluent Flows: Complexity and Algorithms -- Preprocessing Speed-Up Techniques Is Hard -- Communication Requirements for Stable Marriages.
Record Nr. UNISA-996465921603316
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2010
Materiale a stampa
Lo trovi qui: Univ. di Salerno
Opac: Controlla la disponibilità qui
Algorithms and Complexity [[electronic resource] ] : 7th International Conference, CIAC 2010, Rome, Italy, May 26-28, 2010, Proceedings / / edited by Josep Diaz, Tiziana Calamoneri
Algorithms and Complexity [[electronic resource] ] : 7th International Conference, CIAC 2010, Rome, Italy, May 26-28, 2010, Proceedings / / edited by Josep Diaz, Tiziana Calamoneri
Edizione [1st ed. 2010.]
Pubbl/distr/stampa Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2010
Descrizione fisica 1 online resource (XI, 384 p.)
Disciplina 004.0151
Collana Theoretical Computer Science and General Issues
Soggetto topico Computer programming
Computer networks
Computer science
Algorithms
Computer science—Mathematics
Discrete mathematics
Artificial intelligence—Data processing
Programming Techniques
Computer Communication Networks
Theory of Computation
Discrete Mathematics in Computer Science
Data Science
ISBN 1-280-38657-6
9786613564498
3-642-13073-9
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Invited Talks -- Towards a Distributed Search Engine -- Mechanisms for the Marriage and the Assignment Game -- Resilient Algorithms and Data Structures -- Session 1. Graph Algorithms I -- An Exact Algorithm for Connected Red-Blue Dominating Set -- Maximizing PageRank with New Backlinks -- Enumerating Rooted Graphs with Reflectional Block Structures -- Improved Approximations for TSP with Simple Precedence Constraints -- Polynomial Space Algorithms for Counting Dominating Sets and the Domatic Number -- Session 2. Computational Complexity -- Parameterized Complexity of Even/Odd Subgraph Problems -- Popular Matchings in the Marriage and Roommates Problems -- Bounding the Number of Tolerable Faults in Majority-Based Systems -- A Parameterized Algorithm for Chordal Sandwich -- Testing Computability by Width-2 OBDDs Where the Variable Order is Unknown -- Session 3. Graph Coloring -- Graph Unique-Maximum and Conflict-Free Colorings -- Strategic Coloring of a Graph -- Session 4. Tree Algorithms and Tree Decompositions -- Multicut Algorithms via Tree Decompositions -- The Steiner Tree Reoptimization Problem with Sharpened Triangle Inequality -- Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights -- A Planar Linear Arboricity Conjecture -- Session 5. Computational Geometry -- On the Number of Higher Order Delaunay Triangulations -- How Simple Robots Benefit from Looking Back -- Session 6. Game Theory -- On Strategy Improvement Algorithms for Simple Stochastic Games -- Online Cooperative Cost Sharing -- Session 7. Graph Algorithms II -- On the Power of Nodes of Degree Four in the Local Max-Cut Problem -- Packing Bipartite Graphs with Covers of Complete Bipartite Graphs -- Irredundant Set Faster Than O(2 n ) -- The Complexity of Computing Minimal Unidirectional Covering Sets -- A Parameterized Route to Exact Puzzles: Breaking the 2 n -Barrier for Irredundance -- Session 8. String Algorithms -- Finding the Maximum Suffix with Fewer Comparisons -- An Algorithmic Framework for Motif Discovery Problems in Weighted Sequences -- Session 9. Network Algorithms -- Capacitated Confluent Flows: Complexity and Algorithms -- Preprocessing Speed-Up Techniques Is Hard -- Communication Requirements for Stable Marriages.
Record Nr. UNINA-9910483984903321
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2010
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui
Algorithms and Complexity [[electronic resource] ] : 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006, Proceedings / / edited by Tiziana Calamoneri, Irene Finocchi, Guiseppe F. Italiano
Algorithms and Complexity [[electronic resource] ] : 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006, Proceedings / / edited by Tiziana Calamoneri, Irene Finocchi, Guiseppe F. Italiano
Edizione [1st ed. 2006.]
Pubbl/distr/stampa Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2006
Descrizione fisica 1 online resource (XII, 396 p.)
Disciplina 511.8
Collana Theoretical Computer Science and General Issues
Soggetto topico Algorithms
Artificial intelligence—Data processing
Computer science
Computer science—Mathematics
Discrete mathematics
Computer graphics
Data Science
Theory of Computation
Discrete Mathematics in Computer Science
Computer Graphics
ISBN 3-540-34378-4
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Invited Talks -- Reliable and Efficient Geometric Computing -- Beware of the Model: Reflections on Algorithmic Research -- On Search Problems in Complexity Theory and in Logic (Abstract) -- Session 1 -- Covering a Set of Points with a Minimum Number of Lines -- Approximation Algorithms for Capacitated Rectangle Stabbing -- In-Place Randomized Slope Selection -- Session 2 -- Quadratic Programming and Combinatorial Minimum Weight Product Problems -- Counting All Solutions of Minimum Weight Exact Satisfiability -- Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms -- Session 3 -- Network Discovery and Verification with Distance Queries -- Deciding the FIFO Stability of Networks in Polynomial Time -- Heterogenous Networks Can Be Unstable at Arbitrarily Low Injection Rates -- Session 4 -- Provisioning a Virtual Private Network Under the Presence of Non-communicating Groups -- Gathering Algorithms on Paths Under Interference Constraints -- On the Hardness of Range Assignment Problems -- Session 5 -- Black Hole Search in Asynchronous Rings Using Tokens -- On Broadcast Scheduling with Limited Energy -- A Near Optimal Scheduler for On-Demand Data Broadcasts -- Session 6 -- Fair Cost-Sharing Methods for Scheduling Jobs on Parallel Machines -- Tighter Approximation Bounds for LPT Scheduling in Two Special Cases -- Inapproximability Results for Orthogonal Rectangle Packing Problems with Rotations -- Session 7 -- Approximate Hierarchical Facility Location and Applications to the Shallow Steiner Tree and Range Assignment Problems -- An Approximation Algorithm for a Bottleneck Traveling Salesman Problem -- On the Minimum Common Integer Partition Problem -- Session 8 -- Matching Subsequences in Trees -- Distance Approximating Trees: Complexity and Algorithms -- How to Pack Directed Acyclic Graphs into Small Blocks -- Session 9 -- On-Line Coloring of H-Free Bipartite Graphs -- Distributed Approximation Algorithms for Planar Graphs -- A New NC-Algorithm for Finding a Perfect Matching in d-Regular Bipartite Graphs When d Is Small -- Session 10 -- Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments -- Parameterized Algorithms for Hitting Set: The Weighted Case -- Fixed-Parameter Tractable Generalizations of Cluster Editing -- Session 11 -- The Linear Arrangement Problem Parameterized Above Guaranteed Value -- Universal Relations and #P-Completeness -- Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes.
Record Nr. UNISA-996465902403316
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2006
Materiale a stampa
Lo trovi qui: Univ. di Salerno
Opac: Controlla la disponibilità qui
Algorithms and Complexity [[electronic resource] ] : 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006, Proceedings / / edited by Tiziana Calamoneri, Irene Finocchi, Guiseppe F. Italiano
Algorithms and Complexity [[electronic resource] ] : 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006, Proceedings / / edited by Tiziana Calamoneri, Irene Finocchi, Guiseppe F. Italiano
Edizione [1st ed. 2006.]
Pubbl/distr/stampa Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2006
Descrizione fisica 1 online resource (XII, 396 p.)
Disciplina 511.8
Collana Theoretical Computer Science and General Issues
Soggetto topico Algorithms
Artificial intelligence—Data processing
Computer science
Computer science—Mathematics
Discrete mathematics
Computer graphics
Data Science
Theory of Computation
Discrete Mathematics in Computer Science
Computer Graphics
ISBN 3-540-34378-4
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Invited Talks -- Reliable and Efficient Geometric Computing -- Beware of the Model: Reflections on Algorithmic Research -- On Search Problems in Complexity Theory and in Logic (Abstract) -- Session 1 -- Covering a Set of Points with a Minimum Number of Lines -- Approximation Algorithms for Capacitated Rectangle Stabbing -- In-Place Randomized Slope Selection -- Session 2 -- Quadratic Programming and Combinatorial Minimum Weight Product Problems -- Counting All Solutions of Minimum Weight Exact Satisfiability -- Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms -- Session 3 -- Network Discovery and Verification with Distance Queries -- Deciding the FIFO Stability of Networks in Polynomial Time -- Heterogenous Networks Can Be Unstable at Arbitrarily Low Injection Rates -- Session 4 -- Provisioning a Virtual Private Network Under the Presence of Non-communicating Groups -- Gathering Algorithms on Paths Under Interference Constraints -- On the Hardness of Range Assignment Problems -- Session 5 -- Black Hole Search in Asynchronous Rings Using Tokens -- On Broadcast Scheduling with Limited Energy -- A Near Optimal Scheduler for On-Demand Data Broadcasts -- Session 6 -- Fair Cost-Sharing Methods for Scheduling Jobs on Parallel Machines -- Tighter Approximation Bounds for LPT Scheduling in Two Special Cases -- Inapproximability Results for Orthogonal Rectangle Packing Problems with Rotations -- Session 7 -- Approximate Hierarchical Facility Location and Applications to the Shallow Steiner Tree and Range Assignment Problems -- An Approximation Algorithm for a Bottleneck Traveling Salesman Problem -- On the Minimum Common Integer Partition Problem -- Session 8 -- Matching Subsequences in Trees -- Distance Approximating Trees: Complexity and Algorithms -- How to Pack Directed Acyclic Graphs into Small Blocks -- Session 9 -- On-Line Coloring of H-Free Bipartite Graphs -- Distributed Approximation Algorithms for Planar Graphs -- A New NC-Algorithm for Finding a Perfect Matching in d-Regular Bipartite Graphs When d Is Small -- Session 10 -- Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments -- Parameterized Algorithms for Hitting Set: The Weighted Case -- Fixed-Parameter Tractable Generalizations of Cluster Editing -- Session 11 -- The Linear Arrangement Problem Parameterized Above Guaranteed Value -- Universal Relations and #P-Completeness -- Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes.
Record Nr. UNINA-9910484986403321
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2006
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui
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
Opac: Controlla la disponibilità qui
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. UNINA-9910484799203321
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2015
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui
Algorithms and Computation [[electronic resource] ] : 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings / / edited by Hee-Kap Ahn, Chan-Su Shin
Algorithms and Computation [[electronic resource] ] : 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings / / edited by Hee-Kap Ahn, Chan-Su Shin
Edizione [1st ed. 2014.]
Pubbl/distr/stampa Cham : , : Springer International Publishing : , : Imprint : Springer, , 2014
Descrizione fisica 1 online resource (XXII, 781 p. 144 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
Computer science
Discrete Mathematics in Computer Science
Computer Graphics
Data Science
Computer Science
ISBN 3-319-13075-7
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Computational geometry -- Combinatorial optimization -- Graph algorithms -- Enumeration, matching and assignment -- Data structures and algorithms -- Fixed-parameter tractable algorithms -- Scheduling algorithms -- Computational complexity -- Approximation algorithms, graph theory and algorithms -- Online and approximation algorithms -- Network and scheduling algorithms.
Record Nr. UNISA-996210532103316
Cham : , : Springer International Publishing : , : Imprint : Springer, , 2014
Materiale a stampa
Lo trovi qui: Univ. di Salerno
Opac: Controlla la disponibilità qui