6. ISAAC 1995: Cairns, Australia

Invited Presentation

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

Session 1

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

Session 2

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

Session 3A

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

Session 3B

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

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
  
• Vineet Bafna, Piotr Berman, Toshihiro Fujito:
  Constant Ratio Approximations of the Weighted Feedback Vertex Set Problem for Undirected Graphs. 142-151
  
• Magnús M. Halldórsson, Kiyohito Yoshihara:
  Greedy Approximations of Independent Sets in Low Degree Graphs. 152-161
  

Invited Presentation

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

Session 5

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

Session 6

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

Session 7A

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

Session 7B

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

Session 8

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

Invited Presentation

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

Session 9

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

Session 10

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

Session 11A

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

Session 11B

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