6. ISAAC 1995: Cairns, Australia

@proceedings{DBLP:conf/isaac/1995,
  editor    = {John Staples and
               Peter Eades and
               Naoki Katoh and
               Alistair Moffat},
  title     = {Algorithms and Computation, 6th International Symposium, ISAAC
               '95, Cairns, Australia, December 4-6, 1995, Proceedings},
  booktitle = {ISAAC},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1004},
  year      = {1995},
  isbn      = {3-540-60573-8},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Presentation

• Satoru Miyano: Algorithmic Problems Arising from Genome Informatics (Abstract). 1 BibTeX

Session 1

• Shinichi Shimozono: An Approximation Algorithm for Alphabet Indexing Problem. 2-11 BibTeX
• Jyrki Katajainen, Alistair Moffat, Andrew Turpin: A Fast and Space - Economical Algorithm for Length - Limited Coding. 12-21 BibTeX

Session 2

• Binay K. Bhattacharya, Asish Mukhopadhyay: Computing in Linear Time a Chord from Which a Simple Polygon is Weakly Internally Visible. 22-31 BibTeX
• Amitava Datta, Christoph A. Hipke, Sven Schuierer: Competitive Searching in Polygons - Beyond Generalised Streets. 32-41 BibTeX
• Yoshiyuki Kusakari, Hitoshi Suzuki, Takao Nishizeki: Finding a Shortest Pair of Paths on the Plane with Obstacles and Crossing Areas. 42-51 BibTeX

Session 3A

• Satyanarayana V. Lokam, Meena Mahajan, V. Vinay: Logspace Verifiers, NC, and NP. 52-61 BibTeX
• Christoph Karg, Rainer Schuler: Structure in Average Case Complexity. 62-71 BibTeX
• Hank Chien, William L. Steiger: Some Geometric Lower Bounds. 72-81 BibTeX
• Lars Arge: The I/O - Complexity of Ordered Binary - Decision Diagram Manipulation. 82-91 BibTeX

Session 3B

• András Frank, Toshihide Ibaraki, Hiroshi Nagamochi: Two Arc Disjoint Paths in Eulerian Diagraphs. 92-101 BibTeX
• Yuichi Asahiro, Kazuo Iwama: Finding Dense Subgraphs. 102-111 BibTeX
• Arvind Gupta, Naomi Nishimura: finding Smallest Supertrees. 112-121 BibTeX
• Maw-Shang Chang: Weighted Domination on Cocomparability Graphs. 122-131 BibTeX

Sesssion 4

• Alexander E. Andreev, Andrea E. F. Clementi, Pierluigi Crescenzi, Elias Dahlhaus, Sergio De Agostino, José D. P. Rolim: The Parallel Complexity of Approximating the High Degree Subgraph Problem. 132-141 BibTeX
• Vineet Bafna, Piotr Berman, Toshihiro Fujito: Constant Ratio Approximations of the Weighted Feedback Vertex Set Problem for Undirected Graphs. 142-151 BibTeX
• Magnús M. Halldórsson, Kiyohito Yoshihara: Greedy Approximations of Independent Sets in Low Degree Graphs. 152-161 BibTeX

Invited Presentation

• John N. Crossley: Practical Logic (Abstract). 162 BibTeX

Session 5

• Takao Ono, Tomio Hirata, Takao Asano: An Approximation Algorithm for MAX 3-SAT. 163-170 BibTeX
• Sei'ichi Tani, Koichi Yamazaki: Learning of Restricted RNLC Graph Languages. 171-180 BibTeX

Session 6

• Christos H. Papadimitriou, Srinivas Ramanathan, P. Venkat Rangan: Optimal Information Delivery. 181-187 BibTeX
• Nicola Santoro, J. Ren, Amiya Nayak: On the Complexity of Testing for Catastrophic Faults. 188-197 BibTeX
• Oh-Heum Kwon, Kyung-Yong Chwa: Scheduling Parallel Tasks with Individual Deadlines. 198-207 BibTeX

Session 7A

• Joachim von zur Gathen, Igor Shparlinski: Orders of Gauss Periods in Finite Fields. 208-215 BibTeX
• George Havas, Bohdan S. Majewski: A Hard Problem That is Almost Always Easy. 216-223 BibTeX
• Kyoko Sekine, Hiroshi Imai, Seiichiro Tani: Computing the Tutte Polynomial of a Graph of Moderate Size. 224-233 BibTeX
• Jürgen Dedorath, Jordan Gergov, Torben Hagerup: More Efficient Parallel Flow Algorithms. 234-243 BibTeX

Session 7B

• Svante Carlsson, Mikael Sundström: Linear-time In-place Selection in Less than 3n Comparisons. 244-253 BibTeX
• Svante Carlsson, Jingsen Chen: Heap Construction: Optimal in Both Worst and Average Cases? 254-263 BibTeX
• Fei Shi: Fast Approximate Dictionary Matching. 264-273 BibTeX
• Tsan-sheng Hsu: Undirected Vertex-Connectivity Structure and Smallest Four-Vertex-Connectivity Augmentation. 274-283 BibTeX

Session 8

• Peter Damaschke: Searching for a Monotone Function by Independent Threshold Queries. 284-290 BibTeX
• Kazuhisa Makino, Toshihide Ibaraki: A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions. 291-300 BibTeX
• Hsu-Chun Yen, Shi-Tsuen Jian, Ta-Pang Lao: Deciding Bisimulation and Trace Equivalences for Systems with Many Identical Processes. 301-310 BibTeX

Invited Presentation

• Franco P. Preparata: Should Amdahl's Law Be Repealed? (Abstract). 311 BibTeX

Session 9

• Yukihiro Hamada, Aohan Mei, Yasuaki Nishitani, Yoshihide Igarashi: Embeddings of Hyper-Rings in Hypercubes. 312-321 BibTeX
• Siu-Wing Cheng, Chi-Keung Tang: A Fast Algorithm for Computing Optimal Rectilinear Steiner Trees for Extremal Point Sets. 322-331 BibTeX

Session 10

• Xiao Zhou, Takao Nishizeki: Algorithms for Finding f-Colorings of Partial k-Trees. 332-341 BibTeX
• Cho Hwan-Gue, Alexander Zelikovsky: Spanning Closed Trail and Hamiltonian Cycle in Grid Graphs. 342-351 BibTeX
• Wen-Lian Hsu: A Linear Time Algorithm For Finding Maximal Planar Subgraphs. 352-361 BibTeX

Session 11A

• James Abello, Vladimir Estivill-Castro, Thomas C. Shermer, Jorge Urrutia: Illumination with Orthogonal Floodlights. 362-371 BibTeX
• Prosenjit Bose, Godfried T. Toussaint: No Quadrangulation is Extremely Odd. 372-381 BibTeX
• Francis Y. L. Chin, Jack Snoeyink, Cao An Wang: Finding the Medial Axis of a Simple Polygon in Linear Time. 382-391 BibTeX
• Drago Krznaric, Christos Levcopoulos: The First Subquadratic Algorithm for Complete Linkage Clustering. 392-401 BibTeX

Session 11B

• Phillip G. Bradford, Rudolf Fleischer: Matching Nuts and Bolts Faster. 402-408 BibTeX
• James Jianghai Fu: Linear matching-time algorithm for the directed graph isomorphism problem. 409-417 BibTeX
• Satoshi Fujita, Tiko Kameda, Masafumi Yamashita: A Resource Assignment Problem on Graphs. 418-427 BibTeX
• Zhi-Zhong Chen: NC Algorithms for Partitioning Sparse Graphs into Induced Forests with an Application. 428-437 BibTeX