LATIN 2008: Theoretical Informatics 8th Latin American Symposium, Búzios, Brazil, April 7-11, 2008, Proceedings / [electronic resource] :
edited by Eduardo Sany Laber, Claudson Bornstein, Loana Tito Nogueira, Luerbio Faria.
- 1st ed. 2008.
- XVII, 796 p. online resource.
- Theoretical Computer Science and General Issues, 4957 2512-2029 ; .
- Theoretical Computer Science and General Issues, 4957 .
Profile of Tries -- Random 2-XORSAT at the Satisfiability Threshold -- On Dissemination Thresholds in Regular and Irregular Graph Classes -- How to Complete a Doubling Metric -- Sorting and Selection with Random Costs -- Guided Search and a Faster Deterministic Algorithm for 3-SAT -- Comparing and Aggregating Partially Resolved Trees -- Computing the Growth of the Number of Overlap-Free Words with Spectra of Matrices -- On Stateless Multihead Automata: Hierarchies and the Emptiness Problem -- Myhill-Nerode Theorem for Recognizable Tree Series Revisited -- The View Selection Problem for Regular Path Queries -- Optimal Higher Order Delaunay Triangulations of Polygons -- Coloring Geometric Range Spaces -- Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes -- Spanners of Complete k-Partite Geometric Graphs -- Minimum Cost Homomorphisms to Reflexive Digraphs -- On the Complexity of Reconstructing H-free Graphs from Their Star Systems -- Optimization and Recognition for K 5-minor Free Graphs in Linear Time -- Bandwidth of Bipartite Permutation Graphs in Polynomial Time -- The Online Transportation Problem: On the Exponential Boost of One Extra Server -- Average Rate Speed Scaling -- Geometric Aspects of Online Packet Buffering: An Optimal Randomized Algorithm for Two Buffers -- Maximizing the Minimum Load for Selfish Agents -- Approximate Polynomial gcd: Small Degree and Small Height Perturbations -- Pseudorandom Graphs from Elliptic Curves -- Speeding-Up Lattice Reduction with Random Projections (Extended Abstract) -- Sparse Approximate Solutions to Semidefinite Programs -- On the Facets of Mixed Integer Programs with Two Integer Variables and Two Constraints -- A Polyhedral Investigation of the LCS Problem and a Repetition-Free Variant -- Competitive Cost Sharing with Economies of Scale -- Emergency Connectivity in Ad-Hoc Networks with Selfish Nodes -- Fully-Compressed Suffix Trees -- Improved Dynamic Rank-Select Entropy-Bound Structures -- An Improved Algorithm Finding Nearest Neighbor Using Kd-trees -- List Update with Locality of Reference -- Approximating Steiner Networks with Node Weights -- Approximating Minimum-Power Degree and Connectivity Problems -- Energy Efficient Monitoring in Sensor Networks -- Approximation Algorithms for k-Hurdle Problems -- Approximating Crossing Minimization in Radial Layouts -- New Upper Bound on Vertex Folkman Numbers -- Ptolemaic Graphs and Interval Graphs Are Leaf Powers -- A Representation Theorem for Union-Difference Families and Application -- Algorithms to Locate Errors Using Covering Arrays -- On Injective Colourings of Chordal Graphs -- Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms -- On 2-Subcolourings of Chordal Graphs -- Collective Additive Tree Spanners of Homogeneously Orderable Graphs -- The Generalized Median Stable Matchings: Finding Them Is Not That Easy -- Stateless Near Optimal Flow Control with Poly-logarithmic Convergence -- The Least-Unpopularity-Factor and Least-Unpopularity-Margin Criteria for Matching Problems with One-Sided Preferences -- Randomized Rendez-Vous with Limited Memory -- Origami Embedding of Piecewise-Linear Two-Manifolds -- Simplifying 3D Polygonal Chains Under the Discrete Fréchet Distance -- Weighted Rectilinear Approximation of Points in the Plane -- Paths with no Small Angles -- Simpler Constant-Seed Condensers -- Parallel Repetition of the Odd Cycle Game -- I/O-Efficient Point Location in a Set of Rectangles -- Finding Heavy Hitters over the Sliding Window of a Weighted Data Stream -- Fixed-Parameter Algorithms for Cluster VertexDeletion -- Paths and Trails in Edge-Colored Graphs -- Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs -- Domination in Geometric Intersection Graphs -- An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups -- Quantum Property Testing of Group Solvability -- Solving NP-Complete Problems with Quantum Search.
9783540787730
10.1007/978-3-540-78773-0 doi
Computer science.
Algorithms.
Artificial intelligence--Data processing.
Computer science--Mathematics.
Discrete mathematics.
Theory of Computation.
Algorithms.
Data Science.
Discrete Mathematics in Computer Science.
Computer Science Logic and Foundations of Programming.
QA75.5-76.95
004.0151
Profile of Tries -- Random 2-XORSAT at the Satisfiability Threshold -- On Dissemination Thresholds in Regular and Irregular Graph Classes -- How to Complete a Doubling Metric -- Sorting and Selection with Random Costs -- Guided Search and a Faster Deterministic Algorithm for 3-SAT -- Comparing and Aggregating Partially Resolved Trees -- Computing the Growth of the Number of Overlap-Free Words with Spectra of Matrices -- On Stateless Multihead Automata: Hierarchies and the Emptiness Problem -- Myhill-Nerode Theorem for Recognizable Tree Series Revisited -- The View Selection Problem for Regular Path Queries -- Optimal Higher Order Delaunay Triangulations of Polygons -- Coloring Geometric Range Spaces -- Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes -- Spanners of Complete k-Partite Geometric Graphs -- Minimum Cost Homomorphisms to Reflexive Digraphs -- On the Complexity of Reconstructing H-free Graphs from Their Star Systems -- Optimization and Recognition for K 5-minor Free Graphs in Linear Time -- Bandwidth of Bipartite Permutation Graphs in Polynomial Time -- The Online Transportation Problem: On the Exponential Boost of One Extra Server -- Average Rate Speed Scaling -- Geometric Aspects of Online Packet Buffering: An Optimal Randomized Algorithm for Two Buffers -- Maximizing the Minimum Load for Selfish Agents -- Approximate Polynomial gcd: Small Degree and Small Height Perturbations -- Pseudorandom Graphs from Elliptic Curves -- Speeding-Up Lattice Reduction with Random Projections (Extended Abstract) -- Sparse Approximate Solutions to Semidefinite Programs -- On the Facets of Mixed Integer Programs with Two Integer Variables and Two Constraints -- A Polyhedral Investigation of the LCS Problem and a Repetition-Free Variant -- Competitive Cost Sharing with Economies of Scale -- Emergency Connectivity in Ad-Hoc Networks with Selfish Nodes -- Fully-Compressed Suffix Trees -- Improved Dynamic Rank-Select Entropy-Bound Structures -- An Improved Algorithm Finding Nearest Neighbor Using Kd-trees -- List Update with Locality of Reference -- Approximating Steiner Networks with Node Weights -- Approximating Minimum-Power Degree and Connectivity Problems -- Energy Efficient Monitoring in Sensor Networks -- Approximation Algorithms for k-Hurdle Problems -- Approximating Crossing Minimization in Radial Layouts -- New Upper Bound on Vertex Folkman Numbers -- Ptolemaic Graphs and Interval Graphs Are Leaf Powers -- A Representation Theorem for Union-Difference Families and Application -- Algorithms to Locate Errors Using Covering Arrays -- On Injective Colourings of Chordal Graphs -- Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms -- On 2-Subcolourings of Chordal Graphs -- Collective Additive Tree Spanners of Homogeneously Orderable Graphs -- The Generalized Median Stable Matchings: Finding Them Is Not That Easy -- Stateless Near Optimal Flow Control with Poly-logarithmic Convergence -- The Least-Unpopularity-Factor and Least-Unpopularity-Margin Criteria for Matching Problems with One-Sided Preferences -- Randomized Rendez-Vous with Limited Memory -- Origami Embedding of Piecewise-Linear Two-Manifolds -- Simplifying 3D Polygonal Chains Under the Discrete Fréchet Distance -- Weighted Rectilinear Approximation of Points in the Plane -- Paths with no Small Angles -- Simpler Constant-Seed Condensers -- Parallel Repetition of the Odd Cycle Game -- I/O-Efficient Point Location in a Set of Rectangles -- Finding Heavy Hitters over the Sliding Window of a Weighted Data Stream -- Fixed-Parameter Algorithms for Cluster VertexDeletion -- Paths and Trails in Edge-Colored Graphs -- Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs -- Domination in Geometric Intersection Graphs -- An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups -- Quantum Property Testing of Group Solvability -- Solving NP-Complete Problems with Quantum Search.
9783540787730
10.1007/978-3-540-78773-0 doi
Computer science.
Algorithms.
Artificial intelligence--Data processing.
Computer science--Mathematics.
Discrete mathematics.
Theory of Computation.
Algorithms.
Data Science.
Discrete Mathematics in Computer Science.
Computer Science Logic and Foundations of Programming.
QA75.5-76.95
004.0151