Skip to main content
SpringerLink
Log in

Algorithms and Computations

6th International Symposium, ISAAC '95 Cairns, Australia, December 4 - 6, 1995. Proceedings Proceedings.

  • Conference proceedings
  • © 1995

Overview

Editors:
  1. John Staples
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Peter Eades
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Naoki Katoh
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Alistair Moffat
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 1004)

Included in the following conference series:

Conference proceedings info: ISAAC 1995.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (48 papers)

  1. Front Matter

    Download chapter PDF

  2. Algorithmic problems arising from Genome informatics

    • Satoru Miyano
    Pages 1-1

  3. An approximation algorithm for alphabet indexing problem

    • Shinichi Shimozono
    Pages 2-11

  4. A fast and space-economical algorithm for length-limited coding

    • Jyrki Katajainen, Alistair Moffat, Andrew Turpin
    Pages 12-21

  5. Computing in linear time a chord from which a simple polygon is weakly internally visible

    • Binay K. Bhattacharya, Asish Mukhopadhyay
    Pages 22-31

  6. Competitive searching in polygons—Beyond generalised streets

    • Amitava Datta, Christoph A. Hipke, Sven Schuierer
    Pages 32-41

  7. Finding a shortest pair of paths on the plane with obstacles and crossing areas

    • Yoshiyuki Kusakari, Hitoshi Suzuki, Takao Nishizeki
    Pages 42-51

  8. Logspace verifiers, NC, and NP

    • Satyanarayana V. Lokam, Meena Mahajan, V. Vinay
    Pages 52-61

  9. Structure in average case complexity

    • Christoph Karg, Rainer Schuler
    Pages 62-71

  10. Some geometric lower bounds

    • Hank Chien, William Steiger
    Pages 72-81

  11. The I/O-complexity of Ordered Binary-Decision Diagram manipulation

    • Lars Arge
    Pages 82-91

  12. Two arc disjoint paths in Eulerian digraphs

    • András Frank, Toshihide Ibaraki, Hiroshi Nagamochi
    Pages 92-101

  13. Finding dense subgraphs

    • Yuichi Asahiro, Kazuo Iwama
    Pages 102-111

  14. Finding smallest supertrees

    • Arvind Gupta, Naomi Nishimura
    Pages 112-121

  15. Weighted domination on cocomparability graphs

    • Maw-Shang Chang
    Pages 122-131

  16. The parallel complexity of approximating the High Degree Subgraph problem

    • A. E. Andreev, A. Clementi, P. Crescenzi, E. Dahlhaus, S. de Agostino, J. D. P. Rolim
    Pages 132-141

  17. Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs

    • Vineet Bafna, Piotr Berman, Toshihiro Fujito
    Pages 142-151

  18. Greedy approximations of independent sets in low degree graphs

    • Magnús M. Halldórsson, Kiyohito Yoshihara
    Pages 152-161

  19. Practical logic

    • John N. Crossley
    Pages 162-162

  20. An approximation algorithm for MAX 3-SAT

    • Takao Ono, Tomio Hirata, Takao Asano
    Pages 163-170
Back to top

Other volumes

  1. Algorithms and Computations

Keywords

About this book

This book presents the refereed proceedings of the 6th International Symposium on Algorithms and Computation, ISAAC '95, held in Cairns, Australia, in December 1995.
The 45 revised full papers presented together with the abstracts of three invited talks were selected from a total of 130 submissions. The papers address many current aspects of research and advanced applications of algorithms and computations; among the topics covered are graph theory and graph algorithms, computational geometry, computational logics, searching and sorting, approximation and optimization, algebraic manipulation, and coding.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation