Authors:

Alok Aggarwal ⁰,
C. Pandu Rangan ¹

Alok Aggarwal
1. IBM, Solutions Research Center, Block 1 Indian Institute of Technology, New Delhi, India
View author publications

You can also search for this author in PubMed Google Scholar
C. Pandu Rangan
1. Department of Computer Science and Engineering, Indian Institute of Technology, Madras, India
View author publications

You can also search for this author in PubMed Google Scholar

Includes supplementary material: sn.pub/extras

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

27k Accesses
304 Citations
9 Altmetric

Buy it now

eBook USD 39.99

Price excludes VAT (USA)

Softcover Book USD 54.99

Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Learn about institutional subscriptions

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

Table of contents (44 papers)

Front Matter

Pages I-XIII

PDF
Invited Talk
1. The Engineering of Some Bipartite Matching Programs
  
  Kurt Mehlhorn
  
  Pages 1-3
Session 1(a) - Data Structure I
1. General Splay: A Basic Theory and Calculus
  
  G. F. Georgakopoulos, D. J. McClurkin
  
  Pages 4-17
2. Static Dictionaries Supporting Rank
  
  Venkatesh Raman, S. Srinivasa Rao
  
  Pages 18-26
Session 1(b) - Parallel & Distributed Computing I
1. Multiple Spin-Block Decisions
  
  Peter Damaschke
  
  Pages 27-36
2. Asynchronous Random Polling Dynamic Load Balancing
  
  Peter Sanders
  
  Pages 37-48
Session 2(a) - Approximate Algorithm I
1. Simple Approximation Algorithms for MAXNAESP and Hypergraph 2-colarability
  
  Daya Ram Gaur, Ramesh Krishnamurti
  
  Pages 49-55
2. Hardness of Approximating Independent Domination in Circle Graphs
  
  Mirela Damian-Iordache, Sriram V. Pemmaraju
  
  Pages 56-69
3. Constant-Factor Approximation Algorithms for Domination Problems on Circle Graphs
  
  Mirela Damian-Iordache, Sriram V. Pemmaraju
  
  Pages 70-82
Session 2(b) - Computational Intelligence
1. Ordered Binary Decision Diagrams as Knowledge-Bases
  
  Takashi Horiyama, Toshihide Ibaraki
  
  Pages 83-92
2. Hard Tasks for Weak Robots: The Role of Common Knowledge in Pattern Formation by Autonomous Mobile Robots
  
  Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, Peter Widmayer
  
  Pages 93-102
Session 3(a) - Online Algorithm
1. On-Line Load Balancing of Temporary Tasks Revisited
  
  Kar-Keung To, Wai-Ha Wong
  
  Pages 103-112
2. Online Routing in Triangulations
  
  Prosenjit Bose, Pat Morin
  
  Pages 113-122
Session 3(b) - Complexity Theory I
1. The Query Complexity of Program Checking by Constant-Depth Circuits
  
  V. Arvind, K. V. Subrahmanyam, N. V. Vinodchandran
  
  Pages 123-132
2. Tree-Like Resolution Is Superpolynomially Slower Than DAG-Like Resolution for the Pigeonhole Principle
  
  Kazuo Iwama, Shuichi Miyazaki
  
  Pages 133-142
Session 4(a) - Approximate Algorithm II
1. Efficient Approximation Algorithms for Multi-label Map Labeling
  
  Binhai Zhu, C. K. Poon
  
  Pages 143-152
2. Approximation Algorithms in Batch Processing
  
  Xiaotie Deng, Chung Keung Poon, Yuzhong Zhang
  
  Pages 153-162
Session 4(b) - Graph Algorithm I
1. LexBFS-Ordering in Asteroidal Triple-Free Graphs
  
  Jou-Ming Chang, Chin-Wen Ho, Ming-Tat Ko
  
  Pages 163-172
2. Parallel Algorithms for Shortest Paths and Related Problems on Trapezoid Graphs
  
  F. R. Hsu, Yaw-Ling Lin, Yin-Te Tsai
  
  Pages 173-182
Invited Talk
1. Approximation Algorithms for Some Clustering and Classification Problems
  
  Eva Tardos
  
  Pages 183-183

Keywords

Authors and Affiliations

IBM, Solutions Research Center, Block 1 Indian Institute of Technology, New Delhi, India

Alok Aggarwal
Department of Computer Science and Engineering, Indian Institute of Technology, Madras, India

C. Pandu Rangan

Bibliographic Information

Book Title: Algorithms and Computations
Book Subtitle: 10th International Symposium, ISAAC'99, Chennai, India, December 16-18, 1999 Proceedings
Authors: Alok Aggarwal, C. Pandu Rangan
Series Title: Lecture Notes in Computer Science
DOI: https://doi.org/10.1007/3-540-46632-0
Publisher: Springer Berlin, Heidelberg
eBook Packages: Springer Book Archive
Copyright Information: Springer-Verlag Berlin Heidelberg 1999
Softcover ISBN: 978-3-540-66916-6Published: 01 December 1999
eBook ISBN: 978-3-540-46632-1Published: 26 June 2003
Series ISSN: 0302-9743
Series E-ISSN: 1611-3349
Edition Number: 1
Number of Pages: XIV, 454
Topics: Programming Techniques, Mathematics of Computing, Algorithm Analysis and Problem Complexity, Computation by Abstract Devices, Discrete Mathematics in Computer Science, Computer Communication Networks

Publish with us

Policies and ethics

Authors:

Sections

Buy it now

Buying options

Other ways to access

Table of contents (44 papers)

Front Matter

Invited Talk

Session 1(a) - Data Structure I

Session 1(b) - Parallel & Distributed Computing I

Session 2(a) - Approximate Algorithm I

Session 2(b) - Computational Intelligence

Session 3(a) - Online Algorithm

Session 3(b) - Complexity Theory I

Session 4(a) - Approximate Algorithm II

Session 4(b) - Graph Algorithm I

Invited Talk

Keywords

Authors and Affiliations

IBM, Solutions Research Center, Block 1 Indian Institute of Technology, New Delhi, India

Department of Computer Science and Engineering, Indian Institute of Technology, Madras, India

Bibliographic Information

Publish with us

Buy it now

Buying options

Other ways to access

Search

Navigation