Computing and Combinatorics

Invited Talks.- The Web as a Graph: Measurements, Models, and Methods.- Some Observations on the Computational Complexity of Graph Accessibility Problem (Extended Abstract).- Hao Wang Award Paper.- An Approximation for Finding a Smallest 2-Edge-Connected Subgraph Containing a Specified Spanning Tree.- Data Structures.- Theory of 2-3 Heaps.- An External Memory Data Structure for Shortest Path Queries (Extended Abstract).- Computational Biology.- Approximating the Nearest Neighbor Interchange Distance for Evolutionary Trees with Non-uniform Degrees.- Signed Genome Rearrangement by Reversals and Transpositions: Models and Approximations.- Graph Drawing.- An Approximation Algorithm for the Two-Layered Graph Drawing Problem.- Area Minimization for Grid Visibility Representation of Hierarchically Planar Graphs.- Layout Problems on Lattice Graphs.- Discrete Mathematics.- A New Transference Theorem in the Geometry of Numbers.- On Covering and Rank Problems for Boolean Matrices and Their Applications.- A Combinatorial Algorithm for Pfaffians.- Graph Algorithms 1.- How to Swap a Failing Edge of a Single Source Shortest Paths Tree.- On Bounds for the k-Partitioning of Graphs.- A Faster Algorithm for Computing Minimum 5-Way and 6-Way Cuts in Graphs.- Automata and Language.- Probabilities to Accept Languages by Quantum Finite Automata.- Distributionally-Hard Languages.- Circuits and Context-Free Languages.- Complexity Theory and Learning.- On the Negation-Limited Circuit Complexity of Merging.- Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy.- Efficient Learning of Some Linear Matrix Languages.- Combinatorial Optimization 1.- Minimizing Mean Response Time in Batch Processing System.- Approximation Algorithms for Bounded Facility Location.- Scheduling Trees onto Hypercubes and Grids Is NP-complete.- Graph Algorithms 2.- Approximations of Weighted Independent Set and Hereditary Subset Problems.- Multi-coloring Trees.- On the Complexity of