|
Bubblesort and Juggling Sequences |
|
|
1 | (1) |
|
|
|
A Proof of the Molecular Conjecture |
|
|
2 | (2) |
|
|
|
Exact Algorithms for Dominating Clique Problems (Extended Abstract) |
|
|
4 | (10) |
|
|
|
|
|
|
|
|
|
Enumerating Stereoisomers of Tree Structured Molecules Using Dynamic Programming |
|
|
14 | (10) |
|
|
|
|
|
|
|
|
|
Exact Algorithms for the Bottleneck Steiner Tree Problem (Extended Abstract) |
|
|
24 | (10) |
|
|
|
|
|
|
|
|
|
Exact Algorithms for Set Multicover and Multiset Multicover Problems |
|
|
34 | (11) |
|
|
|
|
|
|
|
|
|
Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm |
|
|
45 | (10) |
|
|
|
|
|
|
|
|
|
|
|
|
|
Divide-and-Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems |
|
|
55 | (10) |
|
|
|
|
|
|
|
On Protein Structure Alignment under Distance Constraint |
|
|
65 | (12) |
|
|
|
|
|
A Structural Lemma in 2-Dimensional Packing, and Its Implication on Approximability |
|
|
77 | (10) |
|
|
|
|
|
|
|
|
|
|
|
Max-Coloring Paths: Tight Bounds and Extensions |
|
|
87 | (10) |
|
|
|
|
|
Frechet Distance Problems in Weighted Regions |
|
|
97 | (15) |
|
|
|
|
|
The Complexity of Solving Stochastic Games on Graphs |
|
|
112 | (10) |
|
|
|
|
|
Computational Complexity of Cast Puzzles |
|
|
122 | (10) |
|
|
|
|
|
|
|
|
|
New Bounds on the Average Distance from the Fermat-Weber Center of a Planar Convex Body |
|
|
132 | (10) |
|
|
|
|
|
Reconstructing Numbers from Pairwise Function Values |
|
|
142 | (11) |
|
|
|
|
|
|
|
Hilbert's Thirteenth Problem and Circuit Complexity |
|
|
153 | (10) |
|
Kristoffer Arnsfelt Hansen |
|
|
|
|
|
|
Interval Stabbing Problems in Small Integer Ranges |
|
|
163 | (10) |
|
|
|
Online Sorted Range Reporting |
|
|
173 | (10) |
|
|
|
|
|
|
|
|
|
Data Structures for Approximate Orthogonal Range Counting |
|
|
183 | (10) |
|
|
|
Dynamic 3-Sided Planar Range Queries with Expected Doubly Logarithmic Time |
|
|
193 | (10) |
|
|
|
|
|
|
|
|
|
|
|
Untangled Monotonic Chains and Adaptive Range Search |
|
|
203 | (10) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Geodesic Spanners on Polyhedral Surfaces |
|
|
213 | (11) |
|
|
|
|
|
Approximating Points by a Piecewise Linear Function: I |
|
|
224 | (10) |
|
|
|
|
|
Approximating Points by a Piecewise Linear Function: II. Dealing with Outliers |
|
|
234 | (10) |
|
|
|
|
|
Computing the Map of Geometric Minimal Cuts |
|
|
244 | (11) |
|
|
|
|
|
|
|
On the Camera Placement Problem |
|
|
255 | (10) |
|
|
|
|
|
Graph Orientations with Set Connectivity Requirements |
|
|
265 | (10) |
|
|
|
A Linear Vertex Kernel for MAXIMUM INTERNAL SPANNING TREE |
|
|
275 | (8) |
|
|
|
|
|
|
|
|
|
Geometric Minimum Diameter Minimum Cost Spanning Tree Problem |
|
|
283 | (10) |
|
|
|
|
|
|
|
On Shortest Disjoint Paths in Planar Graphs |
|
|
293 | (10) |
|
|
|
|
|
An Optimal Labeling for Node Connectivity |
|
|
303 | (8) |
|
|
|
|
|
SOFA: Strategyproof Online Frequency Allocation for Multihop Wireless Networks |
|
|
311 | (10) |
|
|
|
|
|
1-Bounded Space Algorithms for 2-Dimensional Bin Packing |
|
|
321 | (10) |
|
|
|
|
|
|
|
On the Advice Complexity of Online Problems (Extended Abstract) |
|
|
331 | (10) |
|
|
|
|
|
|
|
|
|
|
|
Online Knapsack Problems with Limited Cuts |
|
|
341 | (11) |
|
|
|
|
|
Online Paging for Flash Memory Devices |
|
|
352 | (10) |
|
|
|
|
|
|
|
|
|
Shifting Strategy for Geometric Graphs without Geometry |
|
|
362 | (10) |
|
|
|
Approximation Algorithms for Variable Voltage Processors: Min Energy, Max Throughput and Online Heuristics |
|
|
372 | (11) |
|
|
|
Approximation Algorithms for Min-Max Path Cover Problems with Service Handling Time |
|
|
383 | (10) |
|
|
|
|
|
Minimum Covering with Travel Cost |
|
|
393 | (10) |
|
|
|
|
|
|
|
Route-Enabling Graph Orientation Problems |
|
|
403 | (10) |
|
|
|
|
|
|
|
|
|
|
|
Complexity of Approximating the Vertex Centroid of a Polyhedron |
|
|
413 | (10) |
|
|
|
|
|
Popular Matchings with Variable Job Capacities |
|
|
423 | (11) |
|
|
|
|
|
On the Tightness of the Buhraman-Cleve-Wigderson Simulation |
|
|
434 | (7) |
|
|
|
Bounds on Contention Management Algorithms |
|
|
441 | (11) |
|
|
|
|
|
Algorithmic Folding Complexity |
|
|
452 | (10) |
|
|
|
|
|
|
|
|
|
|
|
|
|
Min-Energy Scheduling for Aligned Jobs in Accelerate Model |
|
|
462 | (11) |
|
|
|
|
|
|
|
Posi-modular Systems with Modulotone Requirements under Permutation Constraints |
|
|
473 | (10) |
|
|
|
|
|
Generalized Reduction to Compute Toric Ideals |
|
|
483 | (10) |
|
|
|
|
|
Linear and Sublinear Time Algorithms for Basis of Abelian Groups |
|
|
493 | (10) |
|
|
|
|
|
Good Programming in Transactional Memory Game Theory Meets Multicore Architecture |
|
|
503 | (11) |
|
|
|
|
|
Induced Packing of Odd Cycles in a Planar Graph |
|
|
514 | (10) |
|
|
|
|
|
|
|
|
|
On the Infinitesimal Rigidity of Bar-and-Slider Frameworks |
|
|
524 | (10) |
|
|
|
|
|
Exploration of Periodically Varying Graphs |
|
|
534 | (10) |
|
|
|
|
|
|
|
Parameterized Complexity of Arc-Weighted Directed Steiner Problems |
|
|
544 | (10) |
|
|
|
|
|
|
|
Worst Case Analysis for Pickup and Delivery Problems with Consecutive Pickups and Deliveries |
|
|
554 | (10) |
|
|
|
|
|
Minimum Cycle Bases of Weighted Outerplanar Graphs |
|
|
564 | (9) |
|
|
|
|
|
Bandwidth on At-Free Graphs |
|
|
573 | (10) |
|
|
|
|
|
|
|
|
|
|
|
|
|
Editing Graphs into Disjoint Unions of Dense Clusters |
|
|
583 | (11) |
|
|
|
|
|
|
|
|
|
A Certifying Algorithm for 3-Colorability of P5-Free Graphs |
|
|
594 | (11) |
|
|
|
|
|
|
|
Parameterizing Cut Sets in a Graph by the Number of Their Components |
|
|
605 | (11) |
|
|
|
|
|
|
|
|
|
Inapproximability of Maximal Strip Recovery |
|
|
616 | (10) |
|
|
|
The Complexity of Perfect Matching Problems on Dense Hypergraphs |
|
|
626 | (11) |
|
|
|
|
|
|
|
On Lower Bounds for Constant Width Arithmetic Circuits |
|
|
637 | (10) |
|
|
|
|
|
|
|
Spending is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria |
|
|
647 | (10) |
|
|
|
|
|
The Identity Correspondence Problem and Its Applications |
|
|
657 | (11) |
|
|
|
|
|
Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs |
|
|
668 | (11) |
|
|
|
|
|
|
|
An Improved Approximation Algorithm for the Traveling Tournament Problem |
|
|
679 | (10) |
|
|
|
|
|
|
|
|
|
The Fault-Tolerant Facility Allocation Problem |
|
|
689 | (10) |
|
|
|
|
|
Tighter Approximation Bounds for Minimum CDS in Wireless Ad Hoc Networks |
|
|
699 | (11) |
|
|
|
|
|
|
|
Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms |
|
|
710 | (10) |
|
|
|
|
|
|
|
The Directed Hausdorff Distance between Imprecise Point Sets |
|
|
720 | (10) |
|
|
|
|
|
|
|
|
|
Computing Multidimensional Persistence |
|
|
730 | (10) |
|
|
|
|
|
|
|
Locating an Obnoxious Line among Planar Objects |
|
|
740 | (10) |
|
|
|
|
|
Finding Fullerene Patches in Polynomial Time |
|
|
750 | (10) |
|
|
|
|
|
Convex Drawings of Internally Triconnected Plane Graphs on O(n2) Grids |
|
|
760 | (11) |
|
|
|
|
|
A Self-stabilizing and Local Delaunay Graph Construction |
|
|
771 | (10) |
|
|
|
|
|
|
|
|
|
Succinct Greedy Geometric Routing in the Euclidean Plane |
|
|
781 | (11) |
|
|
|
|
|
Electric Routing and Concurrent Flow Cutting |
|
|
792 | (10) |
|
|
|
|
|
A Polynomial-Time Algorithm for the Universally Quickest Transshipment Problem in a Certain Class of Dynamic Networks with Uniform Path-Lengths |
|
|
802 | (10) |
|
|
|
|
|
Strong Robustness of Randomized Rumor Spreading Protocols |
|
|
812 | (10) |
|
|
|
|
|
|
|
Data Structures for Range Median Queries |
|
|
822 | (10) |
|
|
|
|
|
Deletion without Rebalancing in Multiway Search Trees |
|
|
832 | (10) |
|
|
|
|
|
Counting in the Presence of Memory Faults |
|
|
842 | (10) |
|
|
|
|
|
|
|
|
|
A Simple, Fast, and Compact Static Dictionary |
|
|
852 | (10) |
|
|
|
|
|
Reconstructing Polygons from Scanner Data |
|
|
862 | (10) |
|
|
|
|
|
|
|
Computing Large Matchings in Planar Graphs with Fixed Minimum Degree |
|
|
872 | (10) |
|
|
|
|
|
|
|
Crossing-Free Acyclic Hamiltonian Path Completion for Planar st-Digraphs |
|
|
882 | (10) |
|
|
|
|
|
Covering a Graph with a Constrained Forest (Extended Abstract) |
|
|
892 | (10) |
|
|
|
|
|
|
|
Tri-Edge-Connectivity Augmentation for Planar Straight Line Graphs |
|
|
902 | (11) |
|
|
|
|
|
|
|
|
|
|
|
Upward Star-Shaped Polyhedral Graphs |
|
|
913 | (10) |
|
|
|
|
|
Conditional Hardness of Approximating Satisfiable Max 3CSP-q |
|
|
923 | (10) |
|
|
|
The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata (Extended Abstract) |
|
|
933 | (10) |
|
|
|
Of Choices Failures, and Asynchrony: The Many Faces of Set Agreement |
|
|
943 | (11) |
|
|
|
|
|
|
|
|
|
Step-Assembly with a Constant Number of Tile Types |
|
|
954 | (10) |
|
|
|
|
|
|
|
Lower Bounds on Fast Searching |
|
|
964 | (10) |
|
|
|
|
|
Approximation Algorithms for the Firefighter Problem: Cuts over Time and Submodularity |
|
|
974 | (10) |
|
|
|
|
|
|
|
|
|
Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n1+ε) Time |
|
|
984 | (10) |
|
|
|
|
|
PTAS for k-Tour Cover Problem on the Plane for Moderately Large Values of k |
|
|
994 | (10) |
|
|
|
|
|
|
|
Optimal Randomized Algorithm for the Density Selection Problem |
|
|
1004 | (10) |
|
|
|
|
|
New Results on Simple Stochastic Games |
|
|
1014 | (10) |
|
|
|
|
|
Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences |
|
|
1024 | (10) |
|
|
|
|
|
Succinct Index for Dynamic Dictionary Matching |
|
|
1034 | (10) |
|
|
|
|
|
|
|
|
|
|
|
Range Non-overlapping Indexing |
|
|
1044 | (10) |
|
|
|
|
|
Querying Two Boundary Points for Shortest Paths in a Polygonal Domain (Extended Abstract) |
|
|
1054 | (10) |
|
|
|
|
|
Pattern Matching for 321-Avoiding Permutations |
|
|
1064 | (10) |
|
|
|
|
|
Folding a Better Checkerboard |
|
|
1074 | (10) |
|
|
|
|
|
|
|
|
|
Finding All Approximate Gapped Palindromes |
|
|
1084 | (10) |
|
|
|
|
|
|
|
General Pseudo-random Generators from Weaker Models of Computation |
|
|
1094 | (10) |
|
|
|
Random Generation and Enumeration of Bipartite Permutation Graphs |
|
|
1104 | (10) |
|
|
|
|
|
|
|
|
|
A Combinatorial Algorithm for Horn Programs |
|
|
1114 | (10) |
|
|
|
|
|
Online Maximum Directed Cut |
|
|
1124 | (10) |
|
|
|
|
|
Maintaining Nets and Net Trees under Incremental Motion |
|
|
1134 | (10) |
|
|
|
|
|
|
|
Distributed Scheduling of Parallel Hybrid Computations |
|
|
1144 | (11) |
|
|
|
|
|
Rudrapatna K. Shyamasundar |
|
|
I/O-Efficient Contour Tree Simplification |
|
|
1155 | (11) |
|
|
|
|
|
Algorithms for Computing the Maximum Weight Region Decomposable into Elementary Shapes |
|
|
1166 | (9) |
|
|
|
|
|
|
|
|
|
I/O and Space-Efficient Path Traversal in Planar Graphs |
|
|
1175 | (10) |
|
|
|
|
|
|
|
|
|
Improved Algorithms for Finding Consistent Superstring Based on a New Graph Model |
|
|
1185 | (10) |
|
|
|
|
|
|
|
|
|
Two-Vertex Connectivity Augmentations for Graphs with a Partition Constraint (Extended Abstract) |
|
|
1195 | (10) |
|
|
|
|
|
|
|
|
|
|
|
|
|
Computing a Smallest Multi-labeled Phylogenetic Tree from Rooted Triplets |
|
|
1205 | (10) |
|
|
|
|
|
|
|
On Partitioning a Graph into Two Connected Subgraphs |
|
|
1215 | (10) |
|
|
|
|
| Author Index |
|
1225 | |
