default search action
19th ISAAC 2008: Gold Coast, Australia
- Seok-Hee Hong, Hiroshi Nagamochi, Takuro Fukunaga:
Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008. Proceedings. Lecture Notes in Computer Science 5369, Springer 2008, ISBN 978-3-540-92181-3
Invited Talk
- Tetsuo Asano:
Constant-Working-Space Algorithms: How Fast Can We Solve Problems without Using Any Extra Array?. 1 - Peter Eades:
Some Constrained Notions of Planarity. 2 - Robert Endre Tarjan:
Reachability Problems on Directed Graphs. 3
Approximation Algorithm I
- Zeyu Guo, He Sun, Hong Zhu:
Greedy Construction of 2-Approximation Minimum Manhattan Network. 4-15 - Frank Kammer, Torsten Tholey:
The Complexity of Minimum Convex Coloring. 16-27 - Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara
, Yushi Uno:
On the Complexity of Reconfiguration Problems. 28-39 - Christian Glaßer, Christian Reitwießner, Heinz Schmitz:
Multiobjective Disk Cover Admits a PTAS. 40-51
Online Algorithm
- Sumit Ganguly:
Data Stream Algorithms via Expander Graphs. 52-63 - Shuichi Miyazaki, Kazuya Okamoto:
Improving the Competitive Ratio of the Online OVSF Code Assignment Problem. 64-76 - Weiwei Wu, Minming Li
Optimal Key Tree Structure for Deleting Two or More Leaves. 77-88 - Martin R. Ehmsen, Lene M. Favrholdt, Jens S. Kohrt, Rodica Mihai:
Comparing First-Fit and Next-Fit for Online Edge Coloring. 89-99
Data Structure and Algorithm
- Gerth Stølting Brodal
Selecting Sums in Arrays. 100-111 - Craig Dillabaugh, Meng He
Succinct and I/O Efficient Data Structures for Traversal in Trees. 112-123 - Simon J. Puglisi, Andrew Turpin:
Space-Time Tradeoffs for Longest-Common-Prefix Array Computation. 124-135 - Daniel Raible, Henning Fernau
Power Domination in O*(1.7548n) Using Reference Search Trees. 136-147
Game Theory
- Yingchao Zhao
The Isolation Game: A Game of Distances. 148-158 - Evangelos Bampas
On a Non-cooperative Model for Wavelength Assignment in Multifiber Optical Networks. 159-170 - Shankar Kalyanaraman, Christopher Umans:
The Complexity of Rationalizing Matchings. 171-182 - Panagiota N. Panagopoulou, Paul G. Spirakis:
A Game Theoretic Approach for Efficient Graph Coloring. 183-195
Graph Algorithm I
- Takehiro Ito, Takeaki Uno, Xiao Zhou, Takao Nishizeki:
Partitioning a Weighted Tree to Subtrees of Almost Uniform Size. 196-207 - Mingyu Xiao:
An Improved Divide-and-Conquer Algorithm for Finding All Minimum k-Way Cuts. 208-219 - Michael Lampis, Georgia Kaouri, Valia Mitsou:
On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures. 220-231 - Maxim A. Babenko:
An Efficient Scaling Algorithm for the Minimum Weight Bibranching Problem. 232-245 - Yuta Harada, Hirotaka Ono
The Balanced Edge Cover Problem. 246-257
Fixed Parameter Tractability
- Leizhen Cai, Elad Verbin, Lin Yang:
Firefighting on Trees: (1-1/e)-Approximation, Fixed Parameter Tractability and a Subexponential Algorithm. 258-269 - Joachim Kneis, Alexander Langer, Peter Rossmanith:
A New Algorithm for Finding Trees with Many Leaves. 270-281 - Hans L. Bodlaender
Faster Parameterized Algorithms for Minimum Fill-In. 282-293 - Michael R. Fellows
Graph Layout Problems Parameterized by Vertex Cover. 294-305 - Hans L. Bodlaender
A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs. 306-317
Distributed Algorithm
- Fedor V. Fomin
How to Guard a Graph?. 318-329 - Paola Flocchini, Bernard Mans
Tree Decontamination with Temporary Immunity. 330-341 - Greg Aloupis, Sébastien Collette, Erik D. Demaine, Stefan Langerman
Reconfiguration of Cube-Style Modular Robots Using O(logn) Parallel Moves. 342-353 - Yoann Dieudonné, Franck Petit:
Squaring the Circle with Weak Mobile Robots. 354-365
Database
- Ehsan Chiniforooshan, Arash Farzan, Mehdi Mirzazadeh:
Evaluation of General Set Expressions. 366-377 - Ferdinando Cicalese, Martin Milanic:
Computing with Priced Information: When the Value Makes the Price. 378-389 - Kazuhisa Makino, Hirotaka Ono
Deductive Inference for the Interiors and Exteriors of Horn Theories. 390-401 - Michael R. Fellows
Leaf Powers and Their Properties: Using the Trees. 402-413
Approximation Algorithm II
- Ali Civril
Deterministic Sparse Column Based Matrix Reconstruction via Greedy Approximation of SVD. 414-423 - Naveen Garg
Minimizing Total Flow-Time: The Unrelated Case. 424-435 - Karl Bringmann, Tobias Friedrich:
Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects. 436-447 - Christian Glaßer:
Space-Efficient Informational Redundancy. 448-459
Computational Biology
- Cheng-Wei Luo, Hsiao-Fei Liu, Peng-An Chen, Kun-Mao Chao
Minkowski Sum Selection and Finding. 460-471 - Leo van Iersel, Steven Kelk:
Constructing the Simplest Possible Phylogenetic Network from Triplets. 472-483 - Jaroslaw Byrka, Sylvain Guillemot, Jesper Jansson
New Results on Optimizing Rooted Triplets Consistency. 484-495 - M. Oguzhan Külekci
A Method to Overcome Computer Word Size Limitation in Bit-Parallel Pattern Matching. 496-506
Computational Geometry I
- Ludmila Scharf, Marc Scherfenberg:
Inducing Polygons of Line Arrangements. 507-519 - Danny Z. Chen, Ewa Misiolek:
Free-Form Surface Partition in 3-D. 520-531 - Christian Knauer, Marc Scherfenberg:
Approximate Nearest Neighbor Search under Translation Invariant Hausdorff Distance. 532-543 - Marc J. van Kreveld
Preprocessing Imprecise Points and Splitting Triangulations. 544-555 - Harish Doraiswamy, Vijay Natarajan:
Efficient Output-Sensitive Construction of Reeb Graphs. 556-567
Complexity I
- Jin-yi Cai, Pinyan Lu
Signature Theory in Holographic Algorithms. 568-579 - David Buchfuhrer:
The Complexity of SPP Formula Minimization. 580-591 - Eric Goles Ch., Cedric Little
Understanding a Non-trivial Cellular Automaton by Finding Its Simplest Underlying Communication Protocol. 592-604 - Hiroki Morizumi, Genki Suzuki:
Negation-Limited Inverters of Linear Size. 605-614 - Giovanni Di Crescenzo, Helger Lipmaa
3-Message NP Arguments in the BPK Model with Optimal Soundness and Zero-Knowledge. 615-627
Computational Geometry II
- Jonathan Backer, David G. Kirkpatrick:
A Complete Approximation Algorithm for Shortest Bounded-Curvature Paths. 628-643 - Kevin Buchin
Detecting Commuting Patterns by Clustering Subtrajectories. 644-655 - Prosenjit Bose
On the Stretch Factor of Convex Delaunay Graphs. 656-667 - Hee-Kap Ahn
Covering a Simple Polygon by Monotone Directions. 668-679
Network
- Reid Andersen, Christian Borgs
On the Stability of Web Crawling and Web Search. 680-691 - Tobias Friedrich
Average Update Times for Fully-Dynamic All-Pairs Shortest Paths. 692-703 - Loukas Georgiadis
Computing Frequency Dominators and Related Problems. 704-715 - Shantanu Das, Beat Gfeller, Peter Widmayer:
Computing Best Swaps in Optimal Tree Spanners. 716-727
Optimization
- Hee-Kap Ahn
Covering a Point Set by Two Disjoint Rectangles. 728-739 - Christian Wulff-Nilsen:
Computing the Maximum Detour of a Plane Graph in Subquadratic Time. 740-751 - Harold N. Gabow, Shuxin Nie:
Finding Long Paths, Cycles and Circuits. 752-763 - Jun Luo, Christian Wulff-Nilsen:
Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces. 764-775
Routing
- Basile Couëtoux, Laurent Gourvès, Jérôme Monnot, Orestis Telelis:
On Labeled Traveling Salesman Problems. 776-787 - Feodor F. Dragan, Martín Matamala
Navigating in a Graph by Aid of Its Spanning Tree. 788-799 - Binay K. Bhattacharya, Paz Carmi, Yuzhuang Hu, Qiaosheng Shi:
Single Vehicle Scheduling Problems on Path/Tree/Cycle Networks with Release and Handling Times. 800-811 - Daniel Delling, Giacomo Nannicini:
Bidirectional Core-Based Routing in Dynamic Time-Dependent Road Networks. 812-823
Graph Algorithm II
- Ryuhei Uehara
Bandwidth of Bipartite Permutation Graphs. 824-835 - Sounaka Mishra, Venkatesh Raman, Saket Saurabh, Somnath Sikdar:
König Deletion Sets and Vertex Covers above the Matching Size. 836-847 - Andreas Brandstädt, Tilo Klembt, Vadim V. Lozin
Independent Sets of Maximum Weight in Apple-Free Graphs. 848-858 - Yasuko Matsui, Ryuhei Uehara
Enumeration of Perfect Sequences of Chordal Graph. 859-870 - Vadim V. Lozin
From Tree-Width to Clique-Width: Excluding a Unit Interval Graph. 871-882
Complexity II
- Beate Bollig, Jochen Klump:
New Results on the Most Significant Bit of Integer Multiplication. 883-894 - Felix G. König, Marco E. Lübbecke
Sorting with Complete Networks of Stacks. 895-906 - Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond
Quantum Query Complexity of Boolean Functions with Small On-Sets. 907-918 - Ashley Montanaro
Unbounded-Error Quantum Query Complexity. 919-930 - Rusins Freivalds:
Super-Exponential Size Advantage of Quantum Finite Automata with Mixed States. 931-942
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-01-02 18:25 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: