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 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 | ||
| ||
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 | ||
| ||
Algorithms and Computation : 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings / / edited by Hee-Kap Ahn, Chan-Su Shin
| Algorithms and Computation : 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. | UNINA-9910483162603321 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2014 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Algorithms and Computation [[electronic resource] ] : 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings / / edited by Leizhen Cai, Siu-Wing Cheng, Tak-Wah Lam
| Algorithms and Computation [[electronic resource] ] : 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings / / edited by Leizhen Cai, Siu-Wing Cheng, Tak-Wah Lam |
| Edizione | [1st ed. 2013.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013 |
| Descrizione fisica | 1 online resource (XVIII, 747 p. 145 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-642-45030-X |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Invited Talk Paper -- Market Approach to Social Ads: The MyLikes Example and Related Problems -- Session 1A: Computational Geometry I -- Geodesic-Preserving Polygon Simplification -- Space-Efficient and Data-Sensitive Polygon Reconstruction Algorithms from Visibility Angle Information -- On the Edge Crossing Properties of Euclidean Minimum Weight Laman Graphs -- Structure and Computation of Straight Skeletons in 3-Space -- Session 1B: Pattern Matching -- Pattern Matching with Non Overlapping Reversals – Approximation and On-line Algorithms -- Single and Multiple Consecutive Permutation Motif Search -- Beating O(nm) in Approximate LZW-Compressed Pattern Matching -- Less Space: Indexing for Queries with Wildcards -- Session 2A: Computational Complexity I -- On Determining Deep Holes of Generalized Reed-Solomon Codes -- Isomorphism on Subgraph-Closed Graph Classes: A Complexity Dichotomy and Intermediate Graph Classes -- Determinantal Complexities and Field Extensions -- Session 2B: Internet and Social Network Algorithms I -- Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs -- Sublinear-Time Algorithms for Monomer-Dimer Systems on Bounded Degree Graphs -- The Complexity of Finding a Large Subgraph under Anonymity Constraints -- Session 3A: Graph Theory and Algorithms I -- On the Number of Edges of Fan-Crossing Free Graphs -- Cops and Robbers on Intersection Graphs -- SEFE with No Mapping via Large Induced Outerplane Graphs in Plane Graph -- Hardness and Algorithms for Variants of Line Graphs of Directed Graphs -- Session 3B: Scheduling Algorithms -- Performance Guarantees for Scheduling Algorithms under Perturbed Machine Speeds -- Better Bounds for Online k-Frame Throughput Maximization in Network Switches -- The Solvable Cases of a Scheduling Algorithm -- Session 4A: Computational Complexity II -- Exact Sublinear Binomial Sampling -- Trivial, Tractable, Hard. A Not So Sudden Complexity Jump in Neighborhood Restricted CNF Formulas -- Dynamic Point Labeling is Strongly PSPACE-Complete -- Unsatisfiable CNF Formulas Contain Many Conflicts -- Session 4B: Computational Geometry II -- Pursuit Evasion on Polyhedral Surfaces -- Algorithms for Tolerated Tverberg Partitions -- Abstract Voronoi Diagrams with Disconnected Regions -- Terrain Visibility with Multiple Viewpoints -- Session 5A: Graph Theory and Algorithms II -- Exact Algorithms for Maximum Independent Set -- On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs -- Testing Mutual Duality of Planar Graph -- Session 5B: Fixed-Parameter Tractable Algorithms -- Effective and Efficient Data Reduction for the Subset Interconnection Design Problem -- Myhill-Nerode Methods for Hypergraphs -- Augmenting Graphs to Minimize the Diameter -- Session 6A: Algorithms and Data Structures I -- Top-k Document Retrieval in Compact Space and Near-Optimal Time -- Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers -- Trajectory-Based Dynamic Map Labeling -- Session 6B: Internet and Social Network -- Algorithms II -- Asynchronous Rumor Spreading on Random Graphs -- Unit Cost Buyback Problem -- Faster Rumor Spreading with Multiple Calls -- Session 7A: Algorithmic Game Theory -- Approximating the Value of a Concurrent Reachability Game in the Polynomial Time Hierarchy -- Computing a Walrasian Equilibrium in Iterative Auctions with Multiple Differentiated Items -- New Results on the Online Pricing Problem -- Session 7B: Algorithms and Data Structures II -- RAM-Efficient External Memory Sorting -- Succinct Data Structures for Representing Equivalence Classes -- Sliding Bloom Filters -- Session 8A: Graph Theory and Algorithms III -- Vertex-Weighted Matching in Two-Directional Orthogonal Ray Graphs -- Bounded Representations of Interval and Proper Interval Graphs -- Detecting and Counting Small Pattern Graphs -- An O∗(1.1939n) Time Algorithm for Minimum Weighted Dominating Induced Matching -- Session 8B: Approximation Algorithms I -- New Inapproximability Bounds for TSP -- Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise -- Tight Approximation Bounds for Connectivity with a Color-Spanning Set -- The Train Delivery Problem Revisited -- Session 9A: Computational Geometry III -- The Distance 4-Sector of Two Points Is Unique -- The Number of Different Unfoldings of Polyhedra -- Computing the Smallest Color-Spanning Axis-Parallel Square -- Session 9B: Approximation Algorithms II -- Euclidean Traveling Salesman Tours through Stochastic Neighborhoods -- Detecting and Characterizing Small Dense Bipartite-Like Subgraphs by the Bipartiteness Ratio Measure -- Approximate ˇCech Complex in Low and High Dimensions -- Session 10A: Computational Complexity III -- Model Counting for Formulas of Bounded Clique- Width -- Computing Plurality Points and Condorcet Points in Euclidean Space -- Computing Minimum Tile Sets to Self-assemble Color Patterns -- Session 10B: Network Algorithms -- A Probabilistic Analysis of Kademlia Networks -- Approximating the Generalized Minimum Manhattan Network Problem -- Minmax Regret 1-Facility Location on Uncertain Path Networks. |
| Record Nr. | UNISA-996465647903316 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Algorithms and Computation : 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings / / edited by Leizhen Cai, Siu-Wing Cheng, Tak-Wah Lam
| Algorithms and Computation : 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings / / edited by Leizhen Cai, Siu-Wing Cheng, Tak-Wah Lam |
| Edizione | [1st ed. 2013.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013 |
| Descrizione fisica | 1 online resource (XVIII, 747 p. 145 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-642-45030-X |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Invited Talk Paper -- Market Approach to Social Ads: The MyLikes Example and Related Problems -- Session 1A: Computational Geometry I -- Geodesic-Preserving Polygon Simplification -- Space-Efficient and Data-Sensitive Polygon Reconstruction Algorithms from Visibility Angle Information -- On the Edge Crossing Properties of Euclidean Minimum Weight Laman Graphs -- Structure and Computation of Straight Skeletons in 3-Space -- Session 1B: Pattern Matching -- Pattern Matching with Non Overlapping Reversals – Approximation and On-line Algorithms -- Single and Multiple Consecutive Permutation Motif Search -- Beating O(nm) in Approximate LZW-Compressed Pattern Matching -- Less Space: Indexing for Queries with Wildcards -- Session 2A: Computational Complexity I -- On Determining Deep Holes of Generalized Reed-Solomon Codes -- Isomorphism on Subgraph-Closed Graph Classes: A Complexity Dichotomy and Intermediate Graph Classes -- Determinantal Complexities and Field Extensions -- Session 2B: Internet and Social Network Algorithms I -- Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs -- Sublinear-Time Algorithms for Monomer-Dimer Systems on Bounded Degree Graphs -- The Complexity of Finding a Large Subgraph under Anonymity Constraints -- Session 3A: Graph Theory and Algorithms I -- On the Number of Edges of Fan-Crossing Free Graphs -- Cops and Robbers on Intersection Graphs -- SEFE with No Mapping via Large Induced Outerplane Graphs in Plane Graph -- Hardness and Algorithms for Variants of Line Graphs of Directed Graphs -- Session 3B: Scheduling Algorithms -- Performance Guarantees for Scheduling Algorithms under Perturbed Machine Speeds -- Better Bounds for Online k-Frame Throughput Maximization in Network Switches -- The Solvable Cases of a Scheduling Algorithm -- Session 4A: Computational Complexity II -- Exact Sublinear Binomial Sampling -- Trivial, Tractable, Hard. A Not So Sudden Complexity Jump in Neighborhood Restricted CNF Formulas -- Dynamic Point Labeling is Strongly PSPACE-Complete -- Unsatisfiable CNF Formulas Contain Many Conflicts -- Session 4B: Computational Geometry II -- Pursuit Evasion on Polyhedral Surfaces -- Algorithms for Tolerated Tverberg Partitions -- Abstract Voronoi Diagrams with Disconnected Regions -- Terrain Visibility with Multiple Viewpoints -- Session 5A: Graph Theory and Algorithms II -- Exact Algorithms for Maximum Independent Set -- On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs -- Testing Mutual Duality of Planar Graph -- Session 5B: Fixed-Parameter Tractable Algorithms -- Effective and Efficient Data Reduction for the Subset Interconnection Design Problem -- Myhill-Nerode Methods for Hypergraphs -- Augmenting Graphs to Minimize the Diameter -- Session 6A: Algorithms and Data Structures I -- Top-k Document Retrieval in Compact Space and Near-Optimal Time -- Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers -- Trajectory-Based Dynamic Map Labeling -- Session 6B: Internet and Social Network -- Algorithms II -- Asynchronous Rumor Spreading on Random Graphs -- Unit Cost Buyback Problem -- Faster Rumor Spreading with Multiple Calls -- Session 7A: Algorithmic Game Theory -- Approximating the Value of a Concurrent Reachability Game in the Polynomial Time Hierarchy -- Computing a Walrasian Equilibrium in Iterative Auctions with Multiple Differentiated Items -- New Results on the Online Pricing Problem -- Session 7B: Algorithms and Data Structures II -- RAM-Efficient External Memory Sorting -- Succinct Data Structures for Representing Equivalence Classes -- Sliding Bloom Filters -- Session 8A: Graph Theory and Algorithms III -- Vertex-Weighted Matching in Two-Directional Orthogonal Ray Graphs -- Bounded Representations of Interval and Proper Interval Graphs -- Detecting and Counting Small Pattern Graphs -- An O∗(1.1939n) Time Algorithm for Minimum Weighted Dominating Induced Matching -- Session 8B: Approximation Algorithms I -- New Inapproximability Bounds for TSP -- Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise -- Tight Approximation Bounds for Connectivity with a Color-Spanning Set -- The Train Delivery Problem Revisited -- Session 9A: Computational Geometry III -- The Distance 4-Sector of Two Points Is Unique -- The Number of Different Unfoldings of Polyhedra -- Computing the Smallest Color-Spanning Axis-Parallel Square -- Session 9B: Approximation Algorithms II -- Euclidean Traveling Salesman Tours through Stochastic Neighborhoods -- Detecting and Characterizing Small Dense Bipartite-Like Subgraphs by the Bipartiteness Ratio Measure -- Approximate ˇCech Complex in Low and High Dimensions -- Session 10A: Computational Complexity III -- Model Counting for Formulas of Bounded Clique- Width -- Computing Plurality Points and Condorcet Points in Euclidean Space -- Computing Minimum Tile Sets to Self-assemble Color Patterns -- Session 10B: Network Algorithms -- A Probabilistic Analysis of Kademlia Networks -- Approximating the Generalized Minimum Manhattan Network Problem -- Minmax Regret 1-Facility Location on Uncertain Path Networks. |
| Record Nr. | UNINA-9910483250503321 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Algorithms and Computation [[electronic resource] ] : 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012. Proceedings / / edited by Kun-Mao Chao, Tsan-sheng Hsu, Der-Tsai Lee
| Algorithms and Computation [[electronic resource] ] : 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012. Proceedings / / edited by Kun-Mao Chao, Tsan-sheng Hsu, Der-Tsai Lee |
| Edizione | [1st ed. 2012.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2012 |
| Descrizione fisica | 1 online resource (XVII, 702 p. 117 illus.) |
| Disciplina | 005.1 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Algorithms
Computer science—Mathematics Discrete mathematics Computer networks Computer graphics Artificial intelligence—Data processing Numerical analysis Discrete Mathematics in Computer Science Computer Communication Networks Computer Graphics Data Science Numerical Analysis |
| ISBN | 3-642-35261-8 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Graph algorithms -- online and streaming algorithms -- combinatorial optimization -- computational complexity -- computational geometry -- string algorithms -- approximation algorithms -- graph drawing -- data structures -- randomized algorithms -- algorithmic game theory. |
| Record Nr. | UNISA-996466283903316 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2012 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Algorithms and Computation [[electronic resource] ] : 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings / / edited by Takao Asano, Shin-ichi Nakano, Yoshio Okamoto, Osamu Watanabe
| Algorithms and Computation [[electronic resource] ] : 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings / / edited by Takao Asano, Shin-ichi Nakano, Yoshio Okamoto, Osamu Watanabe |
| Edizione | [1st ed. 2011.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2011 |
| Descrizione fisica | 1 online resource (XVIII, 775 p.) |
| Disciplina | 005.1 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Algorithms
Computer science—Mathematics Discrete mathematics Computer networks Computer graphics Artificial intelligence—Data processing Numerical analysis Discrete Mathematics in Computer Science Computer Communication Networks Computer Graphics Data Science Numerical Analysis |
| ISBN | 3-642-25591-4 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Intro -- Title page -- Preface -- Organization -- Table of Contents -- Invited Talk I -- Algorithm Engineering for Route Planning- An Update - -- References -- Invited Talk II -- Semidefinite Programming and Approximation Algorithms: A Survey -- References -- Approximation Algorithms I -- The School Bus Problem on Trees -- Introduction -- Our Results -- Related Work -- Preliminaries -- A 4-Approximation to the SBP on Trees -- A 12.5-Approximation to the Uncapacitated SBP-R on Trees -- References -- Improved Approximations for Buy-at-Bulk and Shallow-Light k-Steiner Trees and (k, 2)-Subgraph -- Introduction -- Shallow-Light Steiner Trees -- An O(logn)-Approximation for the (k, 2)-Subgraph Problem -- References -- Improved Approximation Algorithms for Routing Shop Scheduling -- Introduction -- Previous Work -- Our Results and Techniques -- Preliminaries -- Routing Open Shop -- Routing Flow Shop -- References -- Contraction-Based Steiner Tree Approximations in Practice -- Introduction -- History -- Contraction Framework -- Algorithm Engineering -- Experiments -- Conclusions and Thoughts -- References -- Computational Geometry I -- Covering and Piercing Disks with Two Centers -- Introduction -- Intersecting Disks with Two Centers -- Decision Algorithm -- Optimization Algorithm -- Covering Disks with Two Centers -- The General Case -- The Restricted Case -- References -- Generating Realistic Roofs over a Rectilinear Polygon -- Introduction -- Preliminaries -- Properties of Realistic Roofs -- Local Properties of Valleys and Ridges -- Global Structure of Realistic Roofs -- Enumerating Realistic Roofs and Computing Optimal Roofs -- References -- Computing the Visibility Polygon Using Few Variables -- Introduction -- Preliminaries -- An O(n) Algorithm Using O(1) Variables -- An O(n logr) Algorithm Using O(logr) Variables -- Closing Remarks.
References -- Minimizing Interference in Ad-Hoc Networks with Bounded Communication Radius -- Introduction -- Definitions and Results -- Layered Nearest Neighbor Algorithm -- Bounded Radius Network -- Conclusion -- References -- Graph Algorithms -- Hamiltonian Paths in the Square of a Tree -- Introduction -- Caterpillars and Horsetails -- 2H-Paths in (u,v)-Horsetails -- Efficient Algorithm for Horstail Queries -- References -- Dominating Induced Matchings for P7-free Graphs in Linear Time -- Introduction and Basic Notions -- Simple Properties of Graphs with Dominating Induced Matching -- Structure of P7-free Graphs with Dominating Induced Matching -- Distance Levels with Respect to an M-Edge in a P3 -- Edges in and between Ti and Tj, i =j -- The Algorithm for the General P7-free Case -- Conclusion -- References -- Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths -- Introduction -- Preliminaries -- Set-Restricted Disjoint Paths -- Contractions and Induced Minors in Chordal Graphs -- Concluding Remarks -- References -- Recognizing Polar Planar Graphs Using New Results for Monopolarity -- Introduction -- Hardness Results -- A 2-SAT Approach and a Superclass of Chair-Free Graphs -- A Superclass of Hole-Free Graphs -- Some Efficiently Solvable Cases of Polarity for Planar Graphs -- Conclusion -- References -- Robustness of Minimum Cost Arborescences -- Introduction -- Fulkerson's Algorithm -- A Sufficient Condition is Necessary -- A Necessary Condition is Sufficient -- References -- Data Structures I -- Path Queries in Weighted Trees -- Introduction -- Previous Work -- Our Results -- Properties of Ordinal Trees -- A Pointer Machine Data Structure -- Optimizations in the RAM model -- Linear Space, but Slower Reporting -- Slightly More Space, Much Faster Reporting -- References -- Dynamic Range Majority Data Structures. Introduction -- Previous Work -- Our Results -- Dynamic Data Structures in One Dimension -- Supporting Queries -- Supporting Updates -- Speedup for Integer Coordinates -- Dynamic Data Structures in Higher Dimensions -- References -- Dynamic Range Selection in Linear Space -- Introduction -- Previous Work -- Our Results -- Linear Space Data Structure -- Space Efficient Ranking Trees -- Answering Queries -- Handling Updates -- Dynamic Arrays -- Concluding Remarks -- References -- A Dynamic Stabbing-Max Data Structure with Sub-Logarithmic Query Time -- Introduction -- A Data Structure with Optimal Query Time -- Compact Representation -- References -- Encoding 2D Range Maximum Queries -- Introduction -- Random Input -- Small m -- Data Structures for 2D-RMQ -- Conclusions and Open Problems -- References -- Distributed Systems -- Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions -- Introduction -- Precise Model and Results -- The Diameter of the Largest Connected Component -- References -- Broadcasting in Heterogeneous Tree Networks with Uncertainty -- Introduction -- Preliminaries -- Finding a Minmax-Regret Broadcast Center -- Correctness -- Time Complexity -- Conclusion -- References -- Optimal File Distribution in Peer-to-Peer Networks -- Introduction -- Homogeneous Symmetric Capacities -- Heterogeneous Symmetric Capacities -- References -- Computational Geometry II -- Animal Testing -- Introduction -- Algorithm 1 Based on Fundamental Polygonsand Davenport-Schinzel Sequences -- Algorithm 2 Based on Euler-Poincaré Formula -- References -- Cutting Out Polygons with a Circular Saw -- Introduction -- Preliminaries -- Algorithm -- References -- Fast Fréchet Queries -- Introduction -- Preliminaries -- The Data Structure -- Making Part of the Query -- Relative Error -- References -- Graph Drawing and Information Visualization. Angle-Restricted Steiner Arborescences for Flow Map Layout -- Introduction -- Optimal Flux Trees -- Spiral Trees -- Computing Spiral Trees -- Approximating Spiral Trees in the Presenceof Obstacles -- Rectilinear Steiner Arborescences -- Spiral Trees -- References -- Treemaps with Bounded Aspect Ratio -- Introduction -- Convex Treemaps -- Ortho-Convex Treemaps -- Conclusions -- References -- Simultaneous Embedding of Embedded Planar Graphs -- Introduction and Overview -- Preliminaries -- Computing a Sefe-Fe of Three Embedded Planar Graphs -- Sefe-Fe and Sge-Fe of k Embedded Graphs Is NP-Hard -- References -- Linear-Time Algorithms for Hole-Free Rectilinear Proportional Contact Graph Representations -- Introduction -- Representations for Maximal Planar Graphs -- Representations of Planar 3-trees -- Representations for Maximal Outer-Planar Graphs -- Conclusion -- References -- Data Structures II -- Fully Retroactive Approximate Range and Nearest Neighbor Searching -- Introduction -- Related Work -- Our Results -- A General Approach to Retroactivity -- Main Results -- References -- Compact Representation of Posets -- Introduction -- Our Work in Context -- Contributions -- Preliminaries -- Posets -- Transitive Reductions -- Succinct Data Structures -- The Representation -- Storing the Chains -- Storing the Order Relation between Chains -- Operations -- Operation reachability(x,y) -- Operations succG(x) and predG(x) -- Operation range(x,y) -- Operation adjGr(x,y) -- Operations succGr(x) and predGr(x) -- Operations a-succGr(x) and a-predGr(x) -- Operations LUB(x1, ..., xt) and GLB(x1, ..., xt) -- Operations a-LUB(x1, ..., xt) and a-GLB(x1, ..., xt) -- Summary and Open Questions -- References -- Explicit Array-Based Compact Data Structures for Triangulations -- Introduction -- Existing Mesh Data Structures -- Preliminaries -- Compactly Representing Triangulations. The First Data Structure: Simple and Still Redundant -- More Compact Solutions, via Minimal Schnyder Woods -- Further Reducing the Space Requirement -- Experimental Results -- References -- Space-Efficient Data-Analysis Queries on Grids -- Introduction -- Wavelet Trees -- Representation of Grids -- Dynamism -- Statistical Queries -- Range Sum, Average, and Variance -- Range Minima and Maxima -- Range Median and Quantiles -- Range Majority -- Range Successor and Predecessor -- Dynamism -- Final Remarks -- References -- Parameterized Algorithms I -- A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments -- Introduction -- Preliminaries -- Modular Partitions -- Reductions and Kernel -- Data Reduction Rules -- Analysis of Kernel Size -- Conclusion -- References -- Fixed-Parameter Complexity of Feedback Vertex Set in Bipartite Tournaments -- Introduction -- Preliminaries -- Canonical Sequence for Acyclic Bipartite Tournament -- Allying Sequence of Node Sets and Increasing Subsequence of Node Sets -- Consistent Node Sequence and Compatible Node Sequence -- A Reduction -- Framework of Our Proof for the Main Lemma -- Good Sequence -- Framework for Proving the Main Lemma -- Dynamic Programming for Proving Lemma 4 -- References -- Parameterized Algorithms for Inclusion of Linear Matchings -- Introduction -- Problem Definition -- Algorithms for Linear Matching Inclusion -- An FPT Algorithm for Parameters d and k -- An FPT Algorithm for Parameter p -- An Algorithm for Nesting-Free Patterns -- Hardness Results -- Hardness of Linear Matching Inclusion -- Hardness of Nesting-Free 2-Interval Pattern -- References -- Computational Study on Bidimensionality Theory Based Algorithm for Longest Path Problem -- Introduction -- Preliminaries -- Algorithms Implemented -- Computational Results -- Results for Longest Paths -- Results for Grid/Cylinder Minors. Concluding Remarks. |
| Record Nr. | UNISA-996466265103316 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2011 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Algorithms and Computation [[electronic resource] ] : 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part II / / edited by Otfried Cheong, Kyung-Yong Chwa, Kunsoo Park
| Algorithms and Computation [[electronic resource] ] : 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part II / / edited by Otfried Cheong, Kyung-Yong Chwa, Kunsoo Park |
| Edizione | [1st ed. 2010.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2010 |
| Descrizione fisica | 1 online resource (XVIII, 474 p. 96 illus.) |
| Disciplina | 005.11 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Computer programming
Algorithms Computer science—Mathematics Discrete mathematics Computer networks Computer graphics Artificial intelligence—Data processing Programming Techniques Discrete Mathematics in Computer Science Computer Communication Networks Computer Graphics Data Science |
| ISBN |
1-280-39061-1
9786613568533 3-642-17514-7 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Session 6A. Data Structure and Algorithm II -- D2-Tree: A New Overlay with Deterministic Bounds -- Efficient Indexes for the Positional Pattern Matching Problem and Two Related Problems over Small Alphabets -- Dynamic Range Reporting in External Memory -- A Cache-Oblivious Implicit Dictionary with the Working Set Property -- Session 6B. Graph Algorithm II -- The (p,q)-total Labeling Problem for Trees -- Drawing a Tree as a Minimum Spanning Tree Approximation -- k-cyclic Orientations of Graphs -- Improved Bounds on the Planar Branchwidth with Respect to the Largest Grid Minor Size -- Session 7A. Computational Geometry II -- Maximum Overlap of Convex Polytopes under Translation -- Approximate Shortest Homotopic Paths in Weighted Regions -- Spanning Ratio and Maximum Detour of Rectilinear Paths in the L 1 Plane -- Session 7B. Graph Coloring II -- Approximation and Hardness Results for the Maximum Edge q-coloring Problem -- 3-Colouring AT-Free Graphs in Polynomial Time -- On Coloring Graphs without Induced Forests -- Session 8A. Approximation Algorithm II -- On the Approximability of the Maximum Interval Constrained Coloring Problem -- Approximability of Constrained LCS -- Approximation Algorithms for the Multi-Vehicle Scheduling Problem -- On Greedy Algorithms for Decision Trees -- Session 8B. Online Algorithm -- Single and Multiple Device DSA Problem, Complexities and Online Algorithms -- The Onion Diagram: A Voronoi-Like Tessellation of a Planar Line Space and Its Applications -- Improved Online Algorithms for 1-Space Bounded 2-Dimensional Bin Packing -- On the Continuous CNN Problem -- Session 9A. Scheduling -- Policies for Periodic Packet Routing -- Increasing Speed Scheduling and Flow Scheduling -- A Tighter Analysis of Work Stealing -- Approximating the Traveling Tournament Problem with Maximum Tour Length 2 -- Session 9B. Data Structure and Algorithm III -- Alphabet Partitioning for Compressed Rank/Select and Applications -- Entropy-Bounded Representation of Point Grids -- Identifying Approximate Palindromes in Run-Length Encoded Strings -- Session 10A. Graph Algorithm III -- Minimum Cost Partitions of Trees with Supply and Demand -- Computing the (t,k)-Diagnosability of Component-Composition Graphs and Its Application -- Why Depth-First Search Efficiently Identifies Two and Three-Connected Graphs -- Beyond Good Shapes: Diffusion-Based Graph Partitioning Is Relaxed Cut Optimization -- Induced Subgraph Isomorphism on Interval and Proper Interval Graphs -- Session 10B. Computational Geometry III -- Testing Simultaneous Planarity When the Common Graph Is 2-Connected -- Computing the Discrete Fréchet Distance with Imprecise Input -- Connectivity Graphs of Uncertainty Regions -- ?/2-Angle Yao Graphs Are Spanners -- Identifying Shapes Using Self-assembly. |
| Record Nr. | UNISA-996466014303316 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2010 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Algorithms and Computation [[electronic resource] ] : 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I / / edited by Otfried Cheong, Kyung-Yong Chwa, Kunsoo Park
| Algorithms and Computation [[electronic resource] ] : 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I / / edited by Otfried Cheong, Kyung-Yong Chwa, Kunsoo Park |
| Edizione | [1st ed. 2010.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2010 |
| Descrizione fisica | 1 online resource (XVIII, 465 p. 66 illus.) |
| Disciplina | 005.11 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Computer programming
Algorithms Computer science—Mathematics Discrete mathematics Computer networks Computer graphics Artificial intelligence—Data processing Programming Techniques Discrete Mathematics in Computer Science Computer Communication Networks Computer Graphics Data Science |
| ISBN |
1-280-39062-X
9786613568540 3-642-17517-1 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Invited Talks -- Regular Labelings and Geometric Structures -- Algorithmic Aspects of Secure Computation and Communication -- Session 1A. Approximation Algorithm I -- Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament -- A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2 -- Approximate Periodicity -- Approximating the Average Stretch Factor of Geometric Graphs -- Session 1B. Complexity I -- Satisfiability with Index Dependency -- Anonymous Fuzzy Identity-Based Encryption for Similarity Search -- Improved Randomized Algorithms for 3-SAT -- Quantum Counterfeit Coin Problems -- Session 2A. Data Structure and Algorithm I -- Priority Range Trees -- Should Static Search Trees Ever Be Unbalanced? -- Levelwise Mesh Sparsification for Shortest Path Queries -- Unit-Time Predecessor Queries on Massive Data Sets -- Session 2B. Combinatorial Optimization -- Popularity at Minimum Cost -- Structural and Complexity Aspects of Line Systems of Graphs -- Neighbor Systems, Jump Systems, and Bisubmodular Polyhedra -- Generating Trees on Multisets -- Session 3A. Graph Algorithm I -- Seidel Minor, Permutation Graphs and Combinatorial Properties -- Simultaneous Interval Graphs -- Unbalanced Graph Partitioning -- On the Intersection of Tolerance and Cocomparability Graphs -- Flows in One-Crossing-Minor-Free Graphs -- Session 3B. Complexity II -- From Holant to #CSP and Back: Dichotomy for Holant c Problems -- Computing Sparse Multiples of Polynomials -- Fractal Parallelism: Solving SAT in Bounded Space and Time -- Interpretation of Stream Programs: Characterizing Type 2 Polynomial Time Complexity -- New Upper Bounds on the Average PTF Density of Boolean Functions -- Session 4A. Computational Geometry I -- An Optimal Algorithm for Computing Angle-Constrained Spanners -- Approximating Minimum Bending Energy Path in a Simple Corridor -- Session 4B. Graph Coloring I -- Analysis of an Iterated Local Search Algorithm for Vertex Coloring -- Bounded Max-colorings of Graphs -- Session 5A. Fixed Parameter Tractability -- Parameterized Algorithms for Boxicity -- On Tractable Cases of Target Set Selection -- Combining Two Worlds: Parameterised Approximation for Vertex Cover -- Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time -- Session 5B. Optimization -- Lower Bounds for Howard’s Algorithm for Finding Minimum Mean-Cost Cycles -- Solving Two-Stage Stochastic Steiner Tree Problems by Two-Stage Branch-and-Cut -- An Optimal Algorithm for Single Maximum Coverage Location on Trees and Related Problems -- A Faster Algorithm for the Maximum Even Factor Problem. |
| Record Nr. | UNISA-996466010103316 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2010 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Algorithms and Computation : 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part II / / edited by Otfried Cheong, Kyung-Yong Chwa, Kunsoo Park
| Algorithms and Computation : 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part II / / edited by Otfried Cheong, Kyung-Yong Chwa, Kunsoo Park |
| Edizione | [1st ed. 2010.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2010 |
| Descrizione fisica | 1 online resource (XVIII, 474 p. 96 illus.) |
| Disciplina | 005.11 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Computer programming
Algorithms Computer science—Mathematics Discrete mathematics Computer networks Computer graphics Artificial intelligence—Data processing Programming Techniques Discrete Mathematics in Computer Science Computer Communication Networks Computer Graphics Data Science |
| ISBN |
1-280-39061-1
9786613568533 3-642-17514-7 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Session 6A. Data Structure and Algorithm II -- D2-Tree: A New Overlay with Deterministic Bounds -- Efficient Indexes for the Positional Pattern Matching Problem and Two Related Problems over Small Alphabets -- Dynamic Range Reporting in External Memory -- A Cache-Oblivious Implicit Dictionary with the Working Set Property -- Session 6B. Graph Algorithm II -- The (p,q)-total Labeling Problem for Trees -- Drawing a Tree as a Minimum Spanning Tree Approximation -- k-cyclic Orientations of Graphs -- Improved Bounds on the Planar Branchwidth with Respect to the Largest Grid Minor Size -- Session 7A. Computational Geometry II -- Maximum Overlap of Convex Polytopes under Translation -- Approximate Shortest Homotopic Paths in Weighted Regions -- Spanning Ratio and Maximum Detour of Rectilinear Paths in the L 1 Plane -- Session 7B. Graph Coloring II -- Approximation and Hardness Results for the Maximum Edge q-coloring Problem -- 3-Colouring AT-Free Graphs in Polynomial Time -- On Coloring Graphs without Induced Forests -- Session 8A. Approximation Algorithm II -- On the Approximability of the Maximum Interval Constrained Coloring Problem -- Approximability of Constrained LCS -- Approximation Algorithms for the Multi-Vehicle Scheduling Problem -- On Greedy Algorithms for Decision Trees -- Session 8B. Online Algorithm -- Single and Multiple Device DSA Problem, Complexities and Online Algorithms -- The Onion Diagram: A Voronoi-Like Tessellation of a Planar Line Space and Its Applications -- Improved Online Algorithms for 1-Space Bounded 2-Dimensional Bin Packing -- On the Continuous CNN Problem -- Session 9A. Scheduling -- Policies for Periodic Packet Routing -- Increasing Speed Scheduling and Flow Scheduling -- A Tighter Analysis of Work Stealing -- Approximating the Traveling Tournament Problem with Maximum Tour Length 2 -- Session 9B. Data Structure and Algorithm III -- Alphabet Partitioning for Compressed Rank/Select and Applications -- Entropy-Bounded Representation of Point Grids -- Identifying Approximate Palindromes in Run-Length Encoded Strings -- Session 10A. Graph Algorithm III -- Minimum Cost Partitions of Trees with Supply and Demand -- Computing the (t,k)-Diagnosability of Component-Composition Graphs and Its Application -- Why Depth-First Search Efficiently Identifies Two and Three-Connected Graphs -- Beyond Good Shapes: Diffusion-Based Graph Partitioning Is Relaxed Cut Optimization -- Induced Subgraph Isomorphism on Interval and Proper Interval Graphs -- Session 10B. Computational Geometry III -- Testing Simultaneous Planarity When the Common Graph Is 2-Connected -- Computing the Discrete Fréchet Distance with Imprecise Input -- Connectivity Graphs of Uncertainty Regions -- ?/2-Angle Yao Graphs Are Spanners -- Identifying Shapes Using Self-assembly. |
| Record Nr. | UNINA-9910483655503321 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2010 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
