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. | 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 |
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 [[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. | 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 |
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 |
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 |
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 |
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 [[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. | UNINA-9910483655603321 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2010 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
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. | UNINA-9910483655503321 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2010 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Algorithms and Computation [[electronic resource] ] : 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings / / edited by Ying Fei Dong, Ding-Zhu Du, Oscar H. Ibarra |
Edizione | [1st ed. 2009.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2009 |
Descrizione fisica | 1 online resource (XXIX, 1228 p.) |
Disciplina | 004n/a |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Artificial intelligence—Data processing
Computer science—Mathematics Mathematics—Data processing Algorithms Discrete mathematics Data Science Mathematics of Computing Computational Mathematics and Numerical Analysis Discrete Mathematics in Computer Science |
ISBN |
1-280-38331-3
9786613561237 3-642-10631-5 |
Classificazione |
DAT 530f
SS 4800 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Bubblesort and Juggling Sequences -- A Proof of the Molecular Conjecture -- Exact Algorithms for Dominating Clique Problems -- Enumerating Stereoisomers of Tree Structured Molecules Using Dynamic Programming -- Exact Algorithms for the Bottleneck Steiner Tree Problem -- Exact Algorithms for Set Multicover and Multiset Multicover Problems -- Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm -- Divide-and-Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems -- On Protein Structure Alignment under Distance Constraint -- A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability -- Max-Coloring Paths: Tight Bounds and Extensions -- Fréchet Distance Problems in Weighted Regions -- The Complexity of Solving Stochastic Games on Graphs -- Computational Complexity of Cast Puzzles -- New Bounds on the Average Distance from the Fermat-Weber Center of a Planar Convex Body -- Reconstructing Numbers from Pairwise Function Values -- Hilbert’s Thirteenth Problem and Circuit Complexity -- Interval Stabbing Problems in Small Integer Ranges -- Online Sorted Range Reporting -- Data Structures for Approximate Orthogonal Range Counting -- Dynamic 3-Sided Planar Range Queries with Expected Doubly Logarithmic Time -- Untangled Monotonic Chains and Adaptive Range Search -- Geodesic Spanners on Polyhedral Surfaces -- Approximating Points by a Piecewise Linear Function: I -- Approximating Points by a Piecewise Linear Function: II. Dealing with Outliers -- Computing the Map of Geometric Minimal Cuts -- On the Camera Placement Problem -- Graph Orientations with Set Connectivity Requirements -- A Linear Vertex Kernel for Maximum Internal Spanning Tree -- Geometric Minimum Diameter Minimum Cost Spanning Tree Problem -- On Shortest Disjoint Paths in Planar Graphs -- An Optimal Labeling for Node Connectivity -- SOFA: Strategyproof Online Frequency Allocation for Multihop Wireless Networks -- 1-Bounded Space Algorithms for 2-Dimensional Bin Packing -- On the Advice Complexity of Online Problems -- Online Knapsack Problems with Limited Cuts -- Online Paging for Flash Memory Devices -- Shifting Strategy for Geometric Graphs without Geometry -- Approximation Algorithms for Variable Voltage Processors: Min Energy, Max Throughput and Online Heuristics -- Approximation Algorithms for Min-Max Path Cover Problems with Service Handling Time -- Minimum Covering with Travel Cost -- Route-Enabling Graph Orientation Problems -- Complexity of Approximating the Vertex Centroid of a Polyhedron -- Popular Matchings with Variable Job Capacities -- On the Tightness of the Buhrman-Cleve-Wigderson Simulation -- Bounds on Contention Management Algorithms -- Algorithmic Folding Complexity -- Min-Energy Scheduling for Aligned Jobs in Accelerate Model -- Posi-modular Systems with Modulotone Requirements under Permutation Constraints -- Generalized Reduction to Compute Toric Ideals -- Linear and Sublinear Time Algorithms for Basis of Abelian Groups -- Good Programming in Transactional Memory -- Induced Packing of Odd Cycles in a Planar Graph -- On the Infinitesimal Rigidity of Bar-and-Slider Frameworks -- Exploration of Periodically Varying Graphs -- Parameterized Complexity of Arc-Weighted Directed Steiner Problems -- Worst Case Analysis for Pickup and Delivery Problems with Consecutive Pickups and Deliveries -- Minimum Cycle Bases of Weighted Outerplanar Graphs -- Bandwidth on AT-Free Graphs -- Editing Graphs into Disjoint Unions of Dense Clusters -- A Certifying Algorithm for 3-Colorability of P 5-Free Graphs -- Parameterizing Cut Sets in a Graph by the Number of Their Components -- Inapproximability of Maximal Strip Recovery -- The Complexity of Perfect Matching Problems on Dense Hypergraphs -- On Lower Bounds for Constant Width Arithmetic Circuits -- Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria -- The Identity Correspondence Problem and Its Applications -- Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs -- An Improved Approximation Algorithm for the Traveling Tournament Problem -- The Fault-Tolerant Facility Allocation Problem -- Tighter Approximation Bounds for Minimum CDS in Wireless Ad Hoc Networks -- Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms -- The Directed Hausdorff Distance between Imprecise Point Sets -- Computing Multidimensional Persistence -- Locating an Obnoxious Line among Planar Objects -- Finding Fullerene Patches in Polynomial Time -- Convex Drawings of Internally Triconnected Plane Graphs on O(n 2) Grids -- A Self-stabilizing and Local Delaunay Graph Construction -- Succinct Greedy Geometric Routing in the Euclidean Plane -- Electric Routing and Concurrent Flow Cutting -- A Polynomial-Time Algorithm for the Universally Quickest Transshipment Problem in a Certain Class of Dynamic Networks with Uniform Path-Lengths -- Strong Robustness of Randomized Rumor Spreading Protocols -- Data Structures for Range Median Queries -- Deletion without Rebalancing in Multiway Search Trees -- Counting in the Presence of Memory Faults -- A Simple, Fast, and Compact Static Dictionary -- Reconstructing Polygons from Scanner Data -- Computing Large Matchings in Planar Graphs with Fixed Minimum Degree -- Crossing-Free Acyclic Hamiltonian Path Completion for Planar st-Digraphs -- Covering a Graph with a Constrained Forest (Extended Abstract) -- Tri-Edge-Connectivity Augmentation for Planar Straight Line Graphs -- Upward Star-Shaped Polyhedral Graphs -- Conditional Hardness of Approximating Satisfiable Max 3CSP-q -- The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata (Extended Abstract) -- Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement -- Step-Assembly with a Constant Number of Tile Types -- Lower Bounds on Fast Searching -- Approximation Algorithms for the Firefighter Problem: Cuts over Time and Submodularity -- Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1?+?? ) Time -- PTAS for k-Tour Cover Problem on the Plane for Moderately Large Values of k -- Optimal Randomized Algorithm for the Density Selection Problem -- New Results on Simple Stochastic Games -- Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences -- Succinct Index for Dynamic Dictionary Matching -- Range Non-overlapping Indexing -- Querying Two Boundary Points for Shortest Paths in a Polygonal Domain -- Pattern Matching for 321-Avoiding Permutations -- Folding a Better Checkerboard -- Finding All Approximate Gapped Palindromes -- General Pseudo-random Generators from Weaker Models of Computation -- Random Generation and Enumeration of Bipartite Permutation Graphs -- A Combinatorial Algorithm for Horn Programs -- Online Maximum Directed Cut -- Maintaining Nets and Net Trees under Incremental Motion -- Distributed Scheduling of Parallel Hybrid Computations -- I/O-Efficient Contour Tree Simplification -- Algorithms for Computing the Maximum Weight Region Decomposable into Elementary Shapes -- I/O and Space-Efficient Path Traversal in Planar Graphs -- Improved Algorithms for Finding Consistent Superstrings Based on a New Graph Model -- Two-Vertex Connectivity Augmentations for Graphs with a Partition Constraint (Extended Abstract) -- Computing a Smallest Multi-labeled Phylogenetic Tree from Rooted Triplets -- On Partitioning a Graph into Two Connected Subgraphs. |
Record Nr. | UNISA-996465913603316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2009 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. di Salerno | ||
|