Acceptance List of ISAAC 2005

ISAAC 2005 Accepted Papers:

(total:112 papers)

33	Title：Finding a Weight-constrained Maximum-density Subtree in a Tree Topic: "graph drawing and graph algorithms"
Authors: "Sun-Yuan Hsieh,Ting-Yu Chou"

41	Title：Fast k-means algorithms with constant approximation Topic: "approximation algorithms"
Authors: "Mingjun Song,Sanguthevar Rajasekaran"

45	Title：Scheduling to minimize makespan with time-dependent processing times Topic: "approximation algorithms"
Authors: "Liying Kang,Erfang Shan"

62	Title：Multi-source Trees: Algorithms for Minimizing Eccentricity Cost Metrics Topic: "graph drawing and graph algorithms"
Authors: "Paraskevi Fragopoulou,Stavros Nikolopoulos,Leonidas Palios"

65	Title：A Min-Max Relation on Packing Feedback Vertex Sets Topic: "combinatorial optimization"
Authors: "Xujin Chen,Guoli Ding,Xiaodong Hu,Wenan Zang"

82	Title：Laminar Structure of Ptolemaic Graphs and Its Applications Topic: "graph drawing and graph algorithms"
Authors: "Ryuhei Uehara,Yushi Uno"

89	Title：Localized and Compact Data-Structure for Comparability Graphs Topic: "data structures"
Authors: "Fabrice Bazzaro,Cyril Gavoille"

90	Title：Finding two disjoint paths in a network with normalized a+-MIN-SUM objective function Topic: "combinatorial optimization"
Authors: "Bing Yang,S.Q. Zheng,Enyue Lu"

93	Title：Dense subgraph problems with output-density conditions} Topic: "approximation algorithms"
Authors: "Akiko Suzuki,Takeshi Tokuyama"

102	Title：On the Complexity of the G-Reconstruction Problem Topic: "computational complexity"
Authors: "Zdenek Dvorak,Vit Jelinek"

108	Title：Simulating algorithms for undirected $st$-connectivity on JAGs and NNJAGs Topic: "computational complexity"
Authors: "Jin-Yi Cai, Pinyan Lu, Chung Keung Poon, Jialin Zhang"

113	Title：A Simple Optimal Randomized Algorithm for Sorting on the PDM Topic: "parallel and distributed algorithms"
Authors: "Sanguthevar RAJASEKARAN,Sandeep Sen"

115	Title：Multi-Directional Width-Bounded Geometric Separator and Protein Folding Topic: "computational geometry"
Authors: "Bin Fu,Sorinel Oprisan,Lizhe Xu"

116	Title：Collective Tree Spanners in Graphs with Bounded Genus, Chordality, Tree-width, or Clique-width Topic: "graph drawing and graph algorithms"
Authors: "Feodor Dragan,Chenyu Yan"

123	Title：A Tight Bound on the Number of Mobile Servers to Guarantee the Mutual Transferability among Dominating Configurations Topic: "parallel and distributed algorithms"
Authors: "Satoshi Fujita"

139	Title：Space efficient algorithms for ordered tree comparison Topic: "computational biology"
Authors: "Lusheng Wang,Kaizhong Zhang"

142	Title：Bounding the Number of Minimal Dominating Sets: a Measure and Conquer Approach Topic: "graph drawing and graph algorithms"
Authors: "Fedor Fomin,Fabrizio grandoni,Pyatkin Pyatkin,Alexey stepanov"

143	Title：Solving Minimum Weight Exact Satisfiability in Time $O(2^{0.2441n})$ Topic: "computational complexity"
Authors: "Stefan Porschen"

173	Title：On efficient weighted rectangle packing with large resources Topic: "approximation algorithms"
Authors: "Alexey Fishkin, Olga Gerber and Klaus Jansen"

180	Title：Randomized Algorithm for the Sum Selection Problem Topic: "randomized algorithms"
Authors: "Tien Ching Lin,D. T. Lee"

188	Title：Improved Algorithms for Largest Cardinality 2-Interval Pattern Problem Topic: "computational biology"
Authors: "Hao Yuan,Linji Yang,Erdong Chen"

193	Title：Minimum Entropy Coloring Topic: "combinatorial optimization"
Authors: "Jean Cardinal,Samuel Fiorini,Gwenaël Joret"

195	Title：Complexity and approximability for the Labeled maximum matching problems: the case of bipartite graphs and perfect matchings Topic: "approximation algorithms"
Authors: "jerome monnot"

198	Title：An Approximation Algorithm for Scheduling Malleable Tasks under General Precedence Constraints Topic: "approximation algorithms"
Authors: "Klaus Jansen,Hu Zhang"

216	Title：On Routing in VLSI Design and Communication Networks Topic: "approximation algorithms"
Authors: "Tamas Terlaky,Anthony Vannelli,Hu Zhang"

223	Title：Drawings of Series-Parallel Graphs with Minimum Bends Topic: "graph drawing and graph algorithms"
Authors: "Xiao Zhou,Takao Nishizeki"

230	Title：Recursion Theoretic Operators for Function Complexity Classes Topic: "computational complexity"
Authors: "Kenya Ueno"

236	Title：On the Complexity of Rocchio's Similarity-Based Relevance Feedback Algorithm Topic: "computational complexity"
Authors: "Zhixiang Chen,Bin Fu"

254	Title：Bisecting a Four-Connected Graph with Three Resource Sets Topic: "graph drawing and graph algorithms"
Authors: "Toshimasa Ishii,Kengo Iwata,Hiroshi Nagamochi"

257	Title：Efficient algorithms for the weighted 2-center problem in a cactus graph Topic: "combinatorial optimization"
Authors: "Qiaosheng Shi,Boaz Benmoshe,Binay Bhattacharya"

261	Title：Longest Increasing Subsequences in Windows based on Canonical Antichain Partition Topic: "data structures"
Authors: "Erdong Chen,Hao Yuan,Linji Yang"

264	Title：Optimal Paths for Mutually Visible Agents Topic: "computational geometry"
Authors: "Joel Fenwick,Vlad Estivill-Castro"

276	Title：From Balls and Bins to Points and Vertices Topic: "computational complexity"
Authors: "Ralf Klasing,Zvi Lotker,Alfredo Navarra,Stephane Perennes"

282	Title：Uniformization of Discrete Data Topic: "experimental algorithm methodologies"
Authors: "Lei Yang"

283	Title：Representation of Graphs by OBDDs Topic: "data structures"
Authors: "Robin Nunkesser,Philipp Woelfel"

286	Title：PSPACE suffices for deciding Nash equilibria properties for extensive games with large trees Topic: "computational complexity"
Authors: "Carme Alvarez,Joaquim Gabarro,Maria Serna"

287	Title：Fast algorithms for finding disjoint subsequences with extremal densities Topic: "computational biology"
Authors: "Anders Bergkvist,Peter Damaschke"

294	Title：A 2-Approximation Algorithm for Capacitated Traveling Salesman Problem with Pickup and Delivery on a Tree} Topic: "approximation algorithms"
Authors: "Andrew Lim,Fan Wang,Zhou Xu"

295	Title：A Complete Characterization of Tolerable Adversary Structures for Secure Point-to-Point Transmissions Topic: "cryptography"
Authors: "Yvo Desmedt,Yongge Wang,Mike Burmester"

296	Title：Minimum Weight Triangulation by Cutting Out Triangles Topic: "computational geometry"
Authors: "Magdalene Grantson,Christian Borgelt,Christos Levcopoulos"

298	Title：Hardness and Approximation of Octilinear Steiner Trees Topic: "approximation algorithms"
Authors: "Matthias Mueller-Hannemann,Anna Schulze"

306	Title：Sampling Unlabeled Biconnected Planar Graphs Topic: "graph drawing and graph algorithms"
Authors: "Manuel Bodirsky, Clemens Gröpl, Mihyun Kang"

307	Title：A Practical Algorithm for the Computation of Market Equilibrium with Logarithmic Utility Functions Topic: "experimental algorithm methodologies"
Authors: "Li-Sha Huang"

309	Title：Computing optimal solutions for the min 3-set covering problem Topic: "combinatorial optimization"
Authors: "Federico Della Croce,Vangelis Paschos"

317	Title：An Improved Interval Routing Scheme for Almost All Networks based on Dominating Cliques Topic: "parallel and distributed algorithms"
Authors: "Martin Nehez,Daniel Olejar"

318	Title：Improved approximate string matching using compressed suffix data structures Topic: "data structures"
Authors: "Tak-Wah Lam,Wing-Kin Sung,Swee-Seong Wong"

319	Title：Complexity of the min-max (regret) versions of cut problems Topic: "combinatorial optimization"
Authors: "Hassene Aissi,Cristina Bazgan,Daniel Vanderpooten"

320	Title：Almost Optimal Solutions for Bin Coloring Problems Topic: "combinatorial optimization"
Authors: "Mingen Lin,Zhiyong Lin,Jinhui Xu"

324	Title：Multiple Polyline to Polygon Matching Topic: "computational geometry"
Authors: "Mirela Tanase,Remco Veltkamp,Herman Haverkort"

326	Title：External Data Structures for Shortest Path Queries on Planar Digraphs Topic: "data structures"
Authors: "Lars Arge,Laura Toma"

332	Title：shortest paths and Voronoi diagrams with transportation networks under general distances Topic: "computational geometry"
Authors: "Sang Won Bae,Kyung-Yong Chwa"

335	Title：Average Case Analysis for Tree Labelling Schemes Topic: "graph drawing and graph algorithms"
Authors: "Weizhao Wang,Xiang-Yang Li,Ming-Yang Kao"

337	Title：Separability with Outliers Topic: "computational geometry"
Authors: "Sariel Har-Peled,Vladlen Koltun"

340	Title：Casting an Object with a Core Topic: "computational geometry"
Authors: "Hee-Kap Ahn,Sang Won Bae,Siu-Wing Cheng,Kyung-Yong Chwa"

357	Title：The Layered Net Surface Problems in Discrete Geometry and Medical Image Segmentation Topic: "computational geometry"
Authors: "Xiaodong Wu,Danny Chen,Kang Li,Milan Sonka"

358	Title：GEN-LARAC: A Generalized Approach to the Constrained Shortest Path Problem under Multiple Additive Constraints Topic: "combinatorial optimization"
Authors: "Ying Xiao,Krishnaiyan Thulasiraman,Guoliang Xue"

361	Title：Minimizing a Monotone Concave Function with Laminar Covering Constraints Topic: "combinatorial optimization"
Authors: "Mariko Sakashita,Kazuhisa Makino,Satoru Fujishige"

374	Title：Monitoring Continuous Band-Join Queries over Dynamic Data Topic: "data structures"
Authors: "Pankaj Agarwal,Junyi Xie,Jun Yang,Hai Yu"

377	Title：Efficient Parallel Algorithms for Constructing a k-Tree Center and a k-Tree Core of a Tree Network Topic: "parallel and distributed algorithms"
Authors: "Yan Wang,Deqiang Wang,Baoyu Tian"

379	Title：Algorithms on the Local Forest Similarity Problem Topic: "computational biology"
Authors: "Peng Zeshan"

384	Title：Smoothed Analysis of Binary Search Trees Topic: "randomized algorithms"
Authors: "Bodo Manthey,Ruediger Reischuk"

388	Title：A 1.75-Approximation Algorithm for Unsigned Translocation Distance Topic: "computational biology"
Authors: "Yun Cui,Lusheng Wang ,Daming Zhu"

389	Title：Preemptive semi-online scheduling on parallel machines with inexact partial information Topic: "online algorithms"
Authors: "Yong He,Yiwei Jiang"

396	Title：On-line computation and maximum-weighted hereditary subgraph problems Topic: "online algorithms"
Authors: "Marc Demange,Bernard Kouakou,Eric Soutif"

402	Title：Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time Topic: "graph drawing and graph algorithms"
Authors: "Seth Pettie"

407	Title：Stacking and bundling two convex polygons Topic: "computational geometry"
Authors: "Hee-Kap Ahn,Otfried Cheong"

408	Title：SkipTree: A Scalable Range-Queryable Distributed Data Structure for Multidimensional Data Topic: "Internet algorithms"
Authors: "Saeed Alaei,Mohammad Toossi,Mohammad Ghodsi"

411	Title：Configurations with Few Crossings in Topological Graphs Topic: "graph drawing and graph algorithms"
Authors: "Christian Knauer,Étienne Schramm,Andreas Spillner,Alexander Wolff"

413	Title：Simple and Efficient Greedy Algorithms for Hamilton Cycles In Random Intersection Graphs Topic: "randomized algorithms"
Authors: "Christoforos Raptopoulos,Paul Spirakis"

415	Title：An Improved $\widetilde{\cal O}(1.234^m)$-Time Deterministic Algorithm for SAT Topic: "combinatorial optimization"
Authors: "Masaki Yamamoto"

418	Title：Counting distinct items over update streams Topic: "randomized algorithms"
Authors: "Sumit Ganguly"

421	Title：Algorithms for Range-Aggregate Query Problems Involving Geometric Aggregation Operations Topic: "computational geometry"
Authors: "Prosenjit Gupta"

431	Title：On the Complexity of Global Constraint Satisfaction Topic: "computational complexity"
Authors: "Cristina Bazgan,Marek Karpinski"

435	Title：A (2-c 1/\sqrt{N})--Approximation Algorithm for the Stable Marriage Problem Topic: "approximation algorithms"
Authors: "Kazuo Iwama,Shuichi Miyazaki,Naoya Yamauchi"

437	Title：Efficient Algorithms for Finding Longest Common Increasing Subsequence Topic: "combinatorial optimization"
Authors: "Wun-Tat Chan,Yong Zhang,Stanley P. Y. Fung,Deshi Ye,Hong Zhu"

439	Title：Fast Algorithms for computing the Tripartition-based Distance between Phylogenetic Networks Topic: "computational biology"
Authors: "Bao Nguyen Nguyen,Cam Thach Nguyen,Wing-Kin Sung"

445	Title：Algorithms for Max Hamming Exact Satisfiability Topic: "combinatorial optimization"
Authors: "Vilhelm Dahllof"

450	Title：Boosting Spectral Partitioning by Sampling and Iteration Topic: "randomized algorithms"
Authors: "Joachim Giesen,Dieter Mitsche"

452	Title：Basic Computations in Wireless Networks Topic: "parallel and distributed algorithms"
Authors: "Ioannis Caragiannis,Clemente Galdi,Christos Kaklamanis"

453	Title：Correlation Clustering and Consensus Clustering Topic: "computational complexity"
Authors: "Paola Bonizzoni,Gianluca Della Vedova,Riccardo Dondi,Tao Jiang"

462	Title：Simultaneous Matchings Topic: "combinatorial optimization"
Authors: "Khaled Elbassioni,Irit Katriel,Martin Kutz,Meena Mahajan"

463	Title：Revisiting T. Uno and M. Yagiura's Algorithm Topic: "graph drawing and graph algorithms"
Authors: "Binh-Minh Bui Xuan,Michel Habib,Christophe Paul"

464	Title：Embedding Point Sets Into Plane Graphs of Small Dilation Topic: "computational geometry"
Authors: "Annette Ebbers-Baumann,Ansgar Gruene,Marek Karpinski,Rolf Klein,Christian Knauer,Andrzej Lingas"

466	Title：Exact and Approximation Algorithms for Computing the Dilation Spectrum of Paths, Trees, and Cycles Topic: "computational geometry"
Authors: "Rolf Klein,Christian Knauer,Giri Narasimhan,Michiel Smid"

467	Title：Drawing Phylogenetic Trees Topic: "graph drawing and graph algorithms"
Authors: "Christian Bachmaier,Ulrik Brandes,Barbara Schlieper"

468	Title：Counting Stable Strategies in Random Evolutionary Games Topic: "combinatorial optimization"
Authors: "Spyros Kontogiannis,Paul Spirakis"

470	Title：Improved Algorithms for the $k$ Maximum-Sums Problems Topic: "combinatorial optimization"
Authors: "Chih-Huai Cheng,Kuan-Yu Chen,Wen-Chin Tien,Kun-Mao Chao"

471	Title：ISB-Tree: A New Indexing Scheme with Efficient Expected Behaviour Topic: "data structures"
Authors: "Alexis Kaporis,Christos Makris,George Mavritsakis,Spyros Sioutas,Athanasios Tsakalidis,Kostas Tsichlas,Christos Zaroliagis"

472	Title：An optimization problem related to VoD broadcasting Topic: "combinatorial optimization"
Authors: "Tiko Kameda"

473	Title：On the Computation of Colored Domino Tilings of Simple and Non-Simple Orthogonal Polygons Topic: "computational geometry"
Authors: "Chris Worman,Boting Yang"

476	Title：Approximating the Traffic Grooming Problem Topic: "approximation algorithms"
Authors: "Michele Flammini,Luca Moscardelli,Mordechai Shalom,Shmuel Zaks"

479	Title：Decision Making Based on Approximate and Smoothed Pareto Curves Topic: "combinatorial optimization"
Authors: "Heiner Ackermann,Alantha Newman,Heiko Roeglin,Berthold Voecking"

480	Title：Generating cut conjunctions and bridge avoiding extensions in graphs Topic: "graph drawing and graph algorithms"
Authors: "Leonid Khachiyan,Endre Boros,Konrad Borys,Khaled Elbassioni,Vladimir Gurvich,Kaz Makino"

481	Title：Approximation Algorithms for Layered Multicast Scheduling Topic: "Internet algorithms"
Authors: "Qingbo Cai,Vincenzo Liberatore"

482	Title：A Network Game with Attacker and Protector Entities Topic: "Internet algorithms"
Authors: "Marios Mavronicolas,Vicky Papadopoulou,Anna Philippou,Paul Spirakis"

484	Title：A 1.5-Approximation of the Minimal Manhattan Network Problem Topic: "approximation algorithms"
Authors: "Sebastian Seibert,Walter Unger"

487	Title：Space-efficient Construction of LZ-index Topic: "data structures"
Authors: "Diego Arroyuelo,Gonzalo Navarro"

488	Title：Sparse geometric graphs with small dilation Topic: "computational geometry"
Authors: "Boris Aronov,Mark de Berg,Otfried Cheong,Joachim Gudmundsson,Herman Haverkort, Antoine Vigneron"

489	Title：Combinatorial Network Abstraction by Trees and Distances Topic: "graph drawing and graph algorithms"
Authors: "Stefan Eckhardt,Sven Kosub,Moritz G. Maaß,Hanjo Täubig,Sebastian Wernicke"

490	Title：Network load games Topic: "combinatorial optimization"
Authors: "Ioannis Caragiannis,Clemente Galdi,Christos Kaklamanis"

491	Title：Hybrid Voting Protocols and Hardness of Manipulation Topic: "computational complexity"
Authors: "Edith Elkind,Helger Lipmaa"

497	Title：Complexity and Approximation of the Minimum Recombination Haplotype Configuration Problem Topic: "computational biology"
Authors: "Lan Liu,Xi Chen,Jing Xiao,Tao Jiang"

498	Title：Approximation Algorithms for Computing the Earth Mover's Distance Under Transformations Topic: "computational geometry"
Authors: "Oliver Klein,Remco C. Veltkamp"

501	Title：On Bounded Load Routings for Modeling k-regular Connection Topologies Topic: "graph drawing and graph algorithms"
Authors: "Adrian Kosowski,Michal Malafiejski,Pawel Zylinski"

508	Title：5th Phylogenetic Root Construction for Strictly Chordal Graphs Topic: "computational biology"
Authors: "William Kennedy,Guohui Lin"

513	Title：The Phase Matrix Topic: "quantum computing"
Authors: "Peter Hoyer"

526	Title：Polynomial Space and Delay Algorithms for Enumeration of Maximal Motifs in a Sequence Topic: "computational biology"
Authors: "Hiroki Arimura,Takeaki Uno"

537	Title：Approximate Colored Range Queries Topic: "data structures"
Authors: "Ying Kit Lai,Chung Keung Poon,Benyun Shi"

545	Title：Distance Labeling in Hyperbolic Graphs Topic: "graph drawing and graph algorithms"
Authors: "Cyril Gavoille, Olivier ly"

547	Title：Upper bounds on the computational power of an optical model of computation Topic: "computational complexity"
Authors: "Damien Woods"

548	Title：A Novel Adaptive Learning Algorithm for Stock Market Prediction Topic: "experimental algorithm methodologies"
Authors: "Lean Yu, Shouyang Wang, Kin Keung Lai"

549	Title：Edge-Pancyclicity of Twisted Cubes Topic: "graph drawing and graph algorithms"
Authors: "Jianxi Fan, Xiaola Lin, Xiaohua Jia"