| |
|
|
|
|
|
|
|
|
1. |
Record Nr. |
UNINA9910483600103321 |
|
|
Titolo |
LATIN 2010: Theoretical Informatics : 9th Latin American Symposium, Oaxaca, Mexico, April 19-23, 2010, Proceedings / / edited by Alejandro López-Ortiz |
|
|
|
|
|
|
|
Pubbl/distr/stampa |
|
|
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2010 |
|
|
|
|
|
|
|
|
|
ISBN |
|
|
|
|
|
|
Edizione |
[1st ed. 2010.] |
|
|
|
|
|
Descrizione fisica |
|
1 online resource (XV, 706 p. 143 illus.) |
|
|
|
|
|
|
Collana |
|
Theoretical Computer Science and General Issues, , 2512-2029 ; ; 6034 |
|
|
|
|
|
|
Altri autori (Persone) |
|
|
|
|
|
|
Disciplina |
|
|
|
|
|
|
Soggetti |
|
Computer programming |
Computer networks |
Computer science |
Algorithms |
Artificial intelligence |
Computer science - Mathematics |
Discrete mathematics |
Programming Techniques |
Computer Communication Networks |
Theory of Computation |
Artificial Intelligence |
Discrete Mathematics in Computer Science |
|
|
|
|
|
|
|
|
Lingua di pubblicazione |
|
|
|
|
|
|
Formato |
Materiale a stampa |
|
|
|
|
|
Livello bibliografico |
Monografia |
|
|
|
|
|
Note generali |
|
Bibliographic Level Mode of Issuance: Monograph |
|
|
|
|
|
|
Nota di bibliografia |
|
Includes bibliographical references and index. |
|
|
|
|
|
|
Nota di contenuto |
|
Continuous and Discrete Methods in Computer Science -- Colorful Strips -- The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions -- Connectivity Is Not a Limit for Kernelization: Planar Connected Dominating Set -- Randomized Truthful Algorithms for Scheduling Selfish Tasks on Parallel Machines -- Almost Linear Time Computation of the Chromatic Polynomial of a Graph of Bounded Tree-Width -- Average Parameterization and Partial Kernelization for Computing Medians -- Sharp Separation and Applications to Exact and Parameterized Algorithms -- Finding the |
|
|
|
|
|
|
|
|
|
|
|
Minimum-Distance Schedule for a Boundary Searcher with a Flashlight -- The Language Theory of Bounded Context-Switching -- Local Search Performance Guarantees for Restricted Related Parallel Machine Scheduling -- Packet Routing on the Grid -- Faithful Representations of Graphs by Islands in the Extended Grid -- The I/O Complexity of Sparse Matrix Dense Matrix Multiplication -- Sparse Recovery Using Sparse Random Matrices -- Optimal Succinctness for Range Minimum Queries -- Compact Rich-Functional Binary Relation Representations -- Radix Cross-Sections for Length Morphisms -- Pairs of Complementary Unary Languages with “Balanced” Nondeterministic Automata -- Quotient Complexity of Ideal Languages -- Complexity of Operations on Cofinite Languages -- Fast Set Intersection and Two-Patterns Matching -- Counting Reducible, Powerful, and Relatively Irreducible Multivariate Polynomials over Finite Fields -- A Larger Lower Bound on the OBDD Complexity of the Most Significant Bit of Multiplication -- Modelling the LLL Algorithm by Sandpiles -- Communication-Efficient Construction of the Plane Localized Delaunay Graph -- Time Complexity of Distributed Topological Self-stabilization: The Case of Graph Linearization -- RandomisedBroadcasting: Memory vs. Randomness -- Limit Theorems for Random MAX-2-XORSAT -- On Quadratic Threshold CSPs -- Finding Lower Bounds on the Complexity of Secret Sharing Schemes by Linear Programming -- Finding the Best CAFE Is NP-Hard -- The Size and Depth of Layered Boolean Circuits -- Lipschitz Unimodal and Isotonic Regression on Paths and Trees -- Ambiguity and Deficiency in Costas Arrays and APN Permutations -- Iterated Shared Memory Models -- Optimal Polygonal Representation of Planar Graphs -- Minimum-Perimeter Intersecting Polygons -- Finding the Smallest Gap between Sums of Square Roots -- Matching Points with Things -- Homotopic Rectilinear Routing with Few Links and Thick Edges -- Tilings Robust to Errors -- Visiting a Sequence of Points with a Bevel-Tip Needle -- Euclidean Prize-Collecting Steiner Forest -- Prize-Collecting Steiner Networks via Iterative Rounding -- Kernelization through Tidying -- Gradual Sub-lattice Reduction and a New Complexity for Factoring Polynomials -- The Power of Fair Pricing Mechanisms -- Quasi-Proportional Mechanisms: Prior-Free Revenue Maximization -- Some Observations on Holographic Algorithms -- The Interval Constrained 3-Coloring Problem -- Counting Hexagonal Patches and Independent Sets in Circle Graphs -- Approximating Maximum Diameter-Bounded Subgraphs -- Largest Induced Acyclic Tournament in Random Digraphs: A 2-Point Concentration -- The Complexity of Counting Eulerian Tours in 4-Regular Graphs -- Efficient Edge Domination on Hole-Free Graphs in Polynomial Time -- Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs -- Rank Selection in Multidimensional Data -- Layered Working-Set Trees -- Lightweight Data Indexing and Compression in External Memory. |
|
|
|
|
|
|
Sommario/riassunto |
|
The papers contained in this volume were presented at the 9th Latin American TheoreticalInformaticsSymposiumheldattheBenitoJu´ arezUniversityofO- aca, Oaxaca City, M´ exico, April 19-23, 2010. The LATIN series of conferences was launched in 1992 to foster the interaction between the Latin American t- oretical computer science community and computer scientists around the world. LATIN 2010wasthe ninth ofa series,after SaoPaulo,Brazil(1992);Valparaiso, Chile (1995); Campinas, Brazil (1998); Punta del Este, Uruguay (2000); C- cun, Mexico (2002); Buenos Aires, Argentina (2004); Valdivia, Chile (2006) and B´ uzios, Rio de Janeiro, Brazil (2008). From the 155 submissions, the Program Committee selected 56 papers for presentation at the conference. The |
|
|
|
|
|
|
|
|
|
|
selectionofpaperswasbasedonoriginality, quality, and relevance to theoretical computer science. It is expected that most of these papers will appear in a more complete and polished form in scienti'c journalsinthefuture.Inadditiontothecontributedpapers,thisvolumecontains the abstracts of four invited plenary talks given at the conference by Cristopher Moore, Piotr Indyk, Sergio Rajsbaum, and Leslie Valiant. A special session on the life and work of the late Imre Simon was held. Prof. Simon played a key role in the development of theoretical computer science in Latin American as well as theLATINconference.ThissessionhadcontributionsfromRicardoBaeza-Yates, John Brzozowski, Volker Diekert, and Jacques Sakarovitch. |
|
|
|
|
|
| |