@article{Satyanarayana-Wood-Camarinopoulos-Pampoukis/96,
AUTHOR = {Satyanarayana, A. and Wood, R.K. and Camarinopoulos, L. and Pampoukis, G.},
TITLE = {Note on ``A linear-time algorithm for computing $k$-terminal reliability in a series-parallel network''},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {2},
PAGES = {290},
YEAR = {1996},
KEYWORDS = {algorithms, complexity, network reliability, series-parallel graphs, reliability-preserving reductions},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Grove-Halpern-Koller/96,
AUTHOR = {Grove, Adam J. and Halpern, Joseph Y. and Koller, Daphne},
TITLE = {Asymptotic conditional probabilities: The unary case},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {1},
PAGES = {1-51},
YEAR = {1996},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Han/96,
AUTHOR = {Han, Yijie},
TITLE = {A fast derandomization scheme and its applications},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {1},
PAGES = {52-82},
YEAR = {1996},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Agarwala-Fernandez-Baca/96a,
AUTHOR = {Agarwala, Richa and Fern{\'{a}}ndez-Baca, David},
TITLE = {Weighted multidimensional search and its application to convex optimization},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {1},
PAGES = {83-99},
YEAR = {1996},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Agarwal-Sharir/96a,
AUTHOR = {Agarwal, Pankaj K. and Sharir, Micha},
TITLE = {Ray shooting amidst convex polyhedra and polyhedral terrains in three dimensions},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {1},
PAGES = {100-116},
YEAR = {1996},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kapron-Cook/96,
AUTHOR = {Kapron, B.M. and Cook, S.A.},
TITLE = {A new characterization of type-2 feasibility},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {1},
PAGES = {117-132},
YEAR = {1996},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Regan/96,
AUTHOR = {Regan, Kenneth W.},
TITLE = {Linear time and memory-efficient computation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {1},
PAGES = {133-168},
YEAR = {1996},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Garg-Vazirani-Yannakakis/96,
AUTHOR = {Garg, Naveen and Vazirani, Vijay V. and Yannakakis, Mihalis},
TITLE = {Approximate max-flow min-(multi)cut theorems and their applications},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {2},
PAGES = {235-251},
YEAR = {1996},
KEYWORDS = {approximation algorithm, multicommodity flow, nimimum multicut},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Rubinfeld-Sudan/96,
AUTHOR = {Rubinfeld, Ronitt and Sudan, Madhu},
TITLE = {Robust characterizations of polynomials with applications to program testing},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {2},
PAGES = {252-271},
YEAR = {1996},
KEYWORDS = {coding theory, program correctness, low-degree polynomial testing},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bafna-Pevzner/96,
AUTHOR = {Bafna, Vineet and Pevzner, Pavel A.},
TITLE = {Genome rearrangements and sorting by reversals},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {2},
PAGES = {272-289},
YEAR = {1996},
KEYWORDS = {computational molecular biology, sorting by reversals, genome rearrangements},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hutton-Lubiw/96,
AUTHOR = {Hutton, Michael D. and Lubiw, Anna},
TITLE = {Upward planar drawing of single-source acyclic digraphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {2},
PAGES = {291-311},
YEAR = {1996},
KEYWORDS = {algorithms, upward planar, graph drawing, graph embedding, graph decomposition, graph recognition, planar graph, directed graph},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ramachandran-Yang/96,
AUTHOR = {Ramachandran, Vijaya and Yang, Honghua},
TITLE = {An efficient parallel algorithm for the general planar monotone circuit value problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {2},
PAGES = {312-339},
YEAR = {1996},
KEYWORDS = {circuit value problem, planar monotone ciruit, plane graph, dual graph, parallel algorithm, EREW PRAM},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chang-Kadin/96,
AUTHOR = {Chang, Richard and Kadin, Jim},
TITLE = {The boolean hierarchy and the polynomial hierarchy: A closer connection},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {2},
PAGES = {340-354},
YEAR = {1996},
KEYWORDS = {polynomial-time hierarchy, Boolean hierarchy, polynomial-time Turing reductions, oracle access, nonuniform algorithms, sparse sets},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Khuller-Raghavachari-Young/96a,
AUTHOR = {Khuller, Samir and Raghavachari, Balaji and Young, Neal},
TITLE = {Low-degree spanning trees of small weight},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {2},
PAGES = {355-368},
YEAR = {1996},
KEYWORDS = {algorithms, spanning trees, approximation algorithms, geometry},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Attiya-Herzberg-Rajsbaum/96,
AUTHOR = {Attiya, Hagit and Herzberg, Amir and Rajsbaum, Sergio},
TITLE = {Optimal clock synchronization under different delay assumptions},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {2},
PAGES = {369-389},
YEAR = {1996},
KEYWORDS = {distributed systems, real-time systems, clock synchronization, message passing systems, networks, optimization, message delay assumptions, precision},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Deng-Hell-Huang/96,
AUTHOR = {Deng, Xiaotie and Hell, Pavol and Huang, Jing},
TITLE = {Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {2},
PAGES = {390-403},
YEAR = {1996},
KEYWORDS = {proper circular-arc graphs, proper interval graphs, local tournaments, representation algorithms},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Rhee-Liang-Dhall-Lakshmivarahan/96,
AUTHOR = {Rhee, C. and Liang, Y.D. and Dhall, S.K. and Lakshmivarahan, S.},
TITLE = {An $O(n+m)$-time algorithm for finding a minimum-weight dominating set in a permutation graph},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {2},
PAGES = {404-419},
YEAR = {1996},
KEYWORDS = {algorithm, dominating set, permutation graph},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Mathur-Reingold/96,
AUTHOR = {Mathur, Anmol and Reingold, Edward M.},
TITLE = {Generalized Kraft's inequality and discrete $k$-modal search},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {2},
PAGES = {420-447},
YEAR = {1996},
KEYWORDS = {$k$-modal search, Kraft's inequality, $k$-modal functions, optimal algorithms, binary search, unimodal search, bimodal search, unbounded search, Fibonacci numbers},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Stearns-Hunt/96,
AUTHOR = {Stearns, Richard E. and Hunt III, Harry B.},
TITLE = {An algebraic model for combinatorial problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {2},
PAGES = {448-476},
YEAR = {1996},
KEYWORDS = {GSP, structure tree, SAT, separator, tree decomposition, treewidth, bounded bandwidth, nonserial optimization, hierarchical specifications},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Irani-Karlin-Phillips/96,
AUTHOR = {Irani, Sandy and Karlin, Anna R. and Phillips, Steven},
TITLE = {Strongly competitive algorithms for paging with locality of reference},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {3},
PAGES = {477-497},
YEAR = {1996},
KEYWORDS = {analysis of algorithms, online algorithms, competitive analysis, paging, locality of reference},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Irani-Rabani/96,
AUTHOR = {Irani, Sandy and Rabani, Yuval},
TITLE = {On the value of coordination in distributed decision making},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {3},
PAGES = {498-519},
YEAR = {1996},
KEYWORDS = {analysis of algorithms, distributed computation, competitive analysis, load balancing, virtual circuit routing},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Condon-Ladner-Lampe-Sinha/96,
AUTHOR = {Condon, Anne and Ladner, Richard and Lampe, Jordan and Sinha, Rakesh},
TITLE = {Complexity of sub-bus mesh computations},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {3},
PAGES = {520-539},
YEAR = {1996},
KEYWORDS = {sub-bus mesh, reconfigurable mesh, time complexity, parity, majority, sum, minimum, CRCW, PRAM, complexity},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kaplan-Shamir/96a,
AUTHOR = {Kaplan, Haim and Shamir, Ron},
TITLE = {Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {3},
PAGES = {540-561},
YEAR = {1996},
KEYWORDS = {design and analysis of algorithms, parameterized complexity, interval graphs, bandwidth, pathwidth},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Friedman-Hershberger-Snoeyink/96,
AUTHOR = {Friedman, J. and Hershberger, J. and Snoeyink, J.},
TITLE = {Efficiently planning compliant motion in the plane},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {3},
PAGES = {562-599},
YEAR = {1996},
KEYWORDS = {computational geometry, compliant motion, path hull data structure},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Arora-Leighton-Maggs/96,
AUTHOR = {Arora, Sanjeev and Leighton, F.T. and Maggs, Bruce M.},
TITLE = {On-line algorithms for path selection in a nonblocking network},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {3},
PAGES = {600-625},
YEAR = {1996},
KEYWORDS = {nonblocking network, multibutterfly network, multi-Bene{\v{s}} network, routing algorithm},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kirousis-Thilikos/96,
AUTHOR = {Kirousis, Lefteris and Thilikos, Dimitris M.},
TITLE = {The linkage of a graph},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {3},
PAGES = {626-647},
YEAR = {1996},
KEYWORDS = {width parameters of a graph, linkage of a graph, backtrack-free search, extremal graph properties, algorithms in NC, P-complete problems},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kannan-Myers/96,
AUTHOR = {Kannan, Sampath K. and Myers, Eugene W.},
TITLE = {An algorithm for locating nonoverlapping regions of maximum alignment score},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {3},
PAGES = {648-662},
YEAR = {1996},
KEYWORDS = {sequence alignment, efficient algorithms, repeated regions},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Jim-Meyer/96,
AUTHOR = {Jim, Trevor and Meyer, Albert R.},
TITLE = {Full abstraction and the context lemma},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {3},
PAGES = {663-696},
YEAR = {1996},
KEYWORDS = {stable functions, full abstraction, Context Lemma, PCF, standardization},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Galil-Park/96,
AUTHOR = {Galil, Zvi and Park, Kunsoo},
TITLE = {Alphabet-independent two-dimensional witness computation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {5},
PAGES = {907-935},
YEAR = {1996},
KEYWORDS = {two-dimensional periodicity, pattern matching, witness computation},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gil-Meyer_auf_der_Heide-Wigderson/96,
AUTHOR = {Gil, Joseph and Meyer auf der Heide, Friedhelm and Wigderson, Avi},
TITLE = {The tree model for hashing: Lower and upper bounds},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {5},
PAGES = {936-955},
YEAR = {1996},
KEYWORDS = {parallel algorithms, randomization, data structures},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{di_Battista-Tamassia/96a,
AUTHOR = {di Battista, Giuseppe and Tamassia, Roberto},
TITLE = {On-line planarity testing},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {5},
PAGES = {956-997},
YEAR = {1996},
KEYWORDS = {planar graph, on-line algorithm, dynamic algorithm},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kedem-Landau-Palem/96,
AUTHOR = {Kedem, Zvi M. and Landau, Gad M. and Palem, Krishna V.},
TITLE = {Parallel suffix-prefix-matching algorithm and applications},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {5},
PAGES = {998-1023},
YEAR = {1996},
KEYWORDS = {amortized complexity, CRCW-PRAMs, multidimensional pattern matching, parallel algorithms, pattern-matching automaton, speedup, string matching},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Aspnes-Waarts/96,
AUTHOR = {Aspnes, James and Waarts, Orli},
TITLE = {Randomized consensus in expected $O(N\log^2 N)$ operations per processor},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {5},
PAGES = {1024-1044},
YEAR = {1996},
KEYWORDS = {consensus, distributed algorithms, shared memory, randomized algorithms, asynchronous computation, martingales},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Fujita-Yamashita/96a,
AUTHOR = {Fujita, Satoshi and Yamashita, Masafumi},
TITLE = {Optimal group gossiping in hypercubes under a circuit-switching model},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {5},
PAGES = {1045-1060},
YEAR = {1996},
KEYWORDS = {parallel algorithm, gossiping, circuit-switching model, optimal-time bound, $n$-cubes},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Pellegrini/96a,
AUTHOR = {Pellegrini, Marco},
TITLE = {On point location and motion planning among simplices},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {5},
PAGES = {1061-1081},
YEAR = {1996},
KEYWORDS = {arrangements of simplices, point location, sparse nets, motion planning, triangulations},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cypher-Konstantinidou/96,
AUTHOR = {Cypher, Robert and Konstantinidou, Smaragda},
TITLE = {Bounds on the efficiency of message-passing protocols for parallel computers},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {5},
PAGES = {1082-1104},
YEAR = {1996},
KEYWORDS = {communication protocols, end-to-end protocols, message passing, parallel computing deadlock},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Shih-Liu/96,
AUTHOR = {Shih, Wei-Kuan and Liu, Jane W.S.},
TITLE = {On-line scheduling of imprecise computations to minimize error},
JOURNAL = {SIAM J. Comput.},
VOLUME = {25},
NUMBER = {5},
PAGES = {1105-1121},
YEAR = {1996},
KEYWORDS = {real-time systems, scheduling to meet deadlines, deterministic scheduling, on-line scheduling},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}