LATIN 2014: Theoretical Informatics: 11th Latin American Symposium, Montevideo, Uruguay, March 31–April 4, 2014. Proceedings

Front Matter....Pages -
Conjugacy in Baumslag’s Group, Generic Case Complexity, and Division in Power Circuits....Pages 1-12
Hierarchical Complexity of 2-Clique-Colouring Weakly Chordal Graphs and Perfect Graphs Having Cliques of Size at Least 3....Pages 13-23
The Computational Complexity of the Game of Set and Its Theoretical Applications....Pages 24-34
Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line....Pages 35-46
Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds....Pages 47-59
False-Name Manipulation in Weighted Voting Games Is Hard for Probabilistic Polynomial Time....Pages 60-71
A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width....Pages 72-83
Optimal Algorithms for Constrained 1-Center Problems....Pages 84-95
A Randomized Incremental Approach for the Hausdorff Voronoi Diagram of Non-crossing Clusters....Pages 96-107
Upper Bounds on the Spanning Ratio of Constrained Theta-Graphs....Pages 108-119
Computing the L 1 Geodesic Diameter and Center of a Simple Polygon in Linear Time....Pages 120-131
The Planar Slope Number of Subcubic Graphs....Pages 132-143
Smooth Orthogonal Drawings of Planar Graphs....Pages 144-155
Drawing HV -Restricted Planar Graphs....Pages 156-167
Periodic Planar Straight-Frame Drawings with Polynomial Resolution....Pages 168-179
A Characterization of Those Automata That Structurally Generate Finite Groups....Pages 180-189
Linear Grammars with One-Sided Contexts and Their Automaton Representation....Pages 190-201
On the Computability of Relations on λ -Terms and Rice’s Theorem - The Case of the Expansion Problem for Explicit Substitutions....Pages 202-213
Computing in the Presence of Concurrent Solo Executions....Pages 214-225
Combining All Pairs Shortest Paths and All Pairs Bottleneck Paths Problems....Pages 226-237
(Total) Vector Domination for Graphs with Bounded Branchwidth....Pages 238-249
Computing the Degeneracy of Large Graphs....Pages 250-260
Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems....Pages 261-272
An Improved Data Stream Algorithm for Clustering....Pages 273-284
Approximation Algorithms for the Gromov Hyperbolicity of Discrete Metric Spaces....Pages 285-293
A (7/2)-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras....Pages 294-305
Helly-Type Theorems in Property Testing....Pages 306-317
New Bounds for Online Packing LPs....Pages 318-329
Improved Minmax Regret 1-Center Algorithms for Cactus Networks with c Cycles....Pages 330-341
Collision-Free Network Exploration....Pages 342-354
Powers of Hamilton Cycles in Pseudorandom Graphs....Pages 355-366
Local Update Algorithms for Random Graphs....Pages 367-378
Odd Graphs Are Prism-Hamiltonian and Have a Long Cycle....Pages 379-390
Relatively Bridge-Addable Classes of Graphs....Pages 391-398
 O ( n ) Time Algorithms for Dominating Induced Matching Problems....Pages 399-408
Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation....Pages 409-420
Convexity in Partial Cubes: The Hull Number....Pages 421-432
Connected Greedy Colourings....Pages 433-441
On the Number of Prefix and Border Tables....Pages 442-453
Probabilities of 2-Xor Functions....Pages 454-465
Equivalence Classes of Random Boolean Trees and Application to the Catalan Satisfiability Problem....Pages 466-477
The Flip Diameter of Rectangulations and Convex Subdivisions....Pages 478-489
Weighted Staircase Tableaux, Asymmetric Exclusion Process, and Eulerian Type Recurrences....Pages 490-501
Counting and Generating Permutations Using Timed Languages....Pages 502-513
Semantic Word Cloud Representations: Hardness and Approximation Algorithms....Pages 514-525
The Complexity of Homomorphisms of Signed Graphs and Signed Constraint Satisfaction....Pages 526-537
Complexity of Coloring Graphs without Paths and Cycles....Pages 538-549
Approximating Real-Time Scheduling on Identical Machines....Pages 550-561
Integrated Supply Chain Management via Randomized Rounding....Pages 562-573
The Online Connected Facility Location Problem....Pages 574-585
Multiply Balanced k  −Partitioning....Pages 586-597
On Some Recent Approximation Algorithms for MAX SAT....Pages 598-609
Packet Forwarding Algorithms in a Line Network....Pages 610-621
Survivability of Swarms of Bouncing Robots....Pages 622-633
Emergence of Wave Patterns on Kadanoff Sandpiles....Pages 634-647
A Divide and Conquer Method to Compute Binomial Ideals....Pages 648-659
How Fast Can We Multiply Large Integers on an Actual Computer?....Pages 660-670
Sorting Permutations by Prefix and Suffix Versions of Reversals and Transpositions....Pages 671-682
Algorithmic and Hardness Results for the Colorful Components Problems....Pages 683-694
On the Stability of Generalized Second Price Auctions with Budgets....Pages 695-706
Approximation Algorithms for the Max-Buying Problem with Limited Supply....Pages 707-718
Budget Feasible Mechanisms for Experimental Design....Pages 719-730
LZ77-Based Self-indexing with Faster Pattern Matching....Pages 731-742
Quad- K -d Trees....Pages 743-754
Biased Predecessor Search....Pages 755-764
Back Matter....Pages -