Publication:4773298
From MaRDI portal
zbMath0286.68029MaRDI QIDQ4773298
Jeffrey D. Ullman, John E. Hopcrofts, A. V. Aho
Publication date: 1969
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
03D05: Automata and formal grammars in connection with logical questions
03D10: Turing machines and related notions
Related Items
Fuzzy linear systems, Efficient computation of an isotonic median regression, Single step searching in weighted block graphs, Cost-optimal parallel algorithms for constructing B-trees, Deterministic improvement of complex polynomial factorization based on the properties of the associated resultant, Computing half-plane and strip discrepancy of planar point sets, The weighted perfect domination problem and its variants, Optimal and nearly optimal algorithms for approximating polynomial zeros, Decomposition of a bidirected graph into strongly connected components and its signed poset structure, Dynamic programming on a functional memory computer, Graph isomorphism and identification matrices: Sequential algorithms, An inversion formula and fast algorithms for Cauchy-Vandermonde matrices, An efficient basis update for asymptotic linear programming, The recognition of union trees, Resource allocation via dynamic programming in activity networks, A linear-time algorithm for computing the intersection of all odd cycles in a graph, Algorithmic aspects of fuzzy control, On Simon's string searching algorithm, Tight comparison bounds for the string prefix-matching problem, Recognition of DFS trees: Sequential and parallel algorithms with refined verifications, Maintenance of 2- and 3-edge-connected components of graphs. I, Cycle structure of edge labelled graphs, On similarity of polynomial configurations, Bipartite bithreshold graphs, Integer sorting on a mesh-connected array of processors, Range-restricted mergeable priority queues, A maximin procedure for the optimal insertion timing of ad executions, An optimal design of piping route in a CAD system for power plant, Time-space tradeoffs for algebraic problems on general sequential machines, Permutation statistics and linear extensions of posets, Smoothness and factoring polynomials over finite fields, Radix sort on the hypercube, Lower bounds for arithmetic problems, On practical algorithms for accelerated matrix multiplication, Parallel priority queues, New clique and independent set algorithms for circle graphs, Expressing combinatorial optimization problems by linear programs, Strings, trees, and patterns, Parallel rectilinear shortest paths with rectangular obstacles, The complexity types of computable sets, Nash and correlated equilibria: Some complexity considerations, The complexity of some graph colouring problems, Hierarchy representations based on arithmetic coding for dynamic information protection systems, A solvable class of quadratic 0-1 programming, The point-to-point delivery and connection problems: Complexity and algorithms, On the problem of multiple mobile robots cluttering a workspace, Random pseudo-polynomial algorithms for some combinatorial programming problems, The traveling salesman problem: An overview of exact and approximate algorithms, A linear-time algorithm for isomorphism of a subclass of chordal graphs, Dynamic output-sensitive hidden surface removal for \(c\)-oriented polyhedra, Lower eigenvalue bounds for singular pencils of matrices, A graph-theoretic heuristic for designing loop-layout manufacturing systems, An approximation algorithm for the general routing problem, Optimal time bounds for some proximity problems in the plane, The parallel complexity of coarsest set partition problems, Sorting on PRAMs with reconfigurable buses, Matching theory -- a sampler: From Dénes König to the present, Solving the Euclidean bottleneck biconnected edge subgraph problem by 2- relative neighborhood graphs, Fault-detection in networks, A fast and efficient parallel algorithm for finding a satisfying truth assignment to a 2-CNF formula, A new upper bound on the complexity of the all pairs shortest path problem, Dense polynomial multiplication with reduced array manipulation overhead, An O\((nm)\) algorithm for a special case of the multimedian location problem on a tree, Degree constrained tree embedding into points in the plane, Fast algorithms for finding Hamiltonian paths and cycles in in-tournament digraphs, A minimum 3-connectivity augmentation of a graph, I/O- and CPU-optimal recognition of strongly connected components, An \(O(m\log n)\) algorithm for the max+sum spanning tree problem, LP relaxation of the two dimensional knapsack problem with box and GUB constraints, Total completion time minimization in two-machine job shops with unit-time operations, The partial sum criterion for Steiner trees in graphs and shortest paths, Minimal vertex separators of chordal graphs, Large computation of the maximum rank correlation estimator, Sentences over integral domains and their computational complexities, Decompositions to degree-constrained subgraphs are simply reducible to edge-colorings, Uncovering generalized-network structure in matrices, Generating the best \(K\) sequences in relocation problems, A note on the tour problems in two-terminal series-parallel graphs, Irreversibility problem in NL-class relations, On the Euclidean two paths problem, Displacement structure of pseudoinverses, Bin-packing by simulated annealing, Key generation of algebraic-code cryptosystems, An \(O(nm)\)-time algorithm for computing the dual of a regular Boolean function, An optimal algorithm to compute all the covers of a string, Complexity of multiplication with vectors for structured matrices, A clustering heuristic to detect staircase structures in large scale linear programming models, Linear recognition of pseudo-split graphs, Bounds on certain multiplications of affine combinations, An algebraic approach for morphological operations on 2D and 3D images, On the complexity of computing Gröbner bases in characteristic 2, On the equivalence of constrained and unconstrained flows, A data structure for bicategories, with application to speeding up an approximation algorithm, Search problems: One, two or many rounds, The determinant of a tree's neighborhood matrix, On semi-\(P_ 4\)-sparse graphs, Generalized coloring for tree-like graphs, Minimum dispersion problems, Numerical database system based on a weighted search tree, Algebraic and numerical techniques for the computation of matrix determinants, Optimal channel allocation for several types of cellular radio networks, Hamiltonian cycles in circulant digraphs with two stripes, Edge-packing planar graphs by cyclic graphs, The algorithmic use of hypertree structure and maximum neighbourhood orderings, A real-time parallel application: The detection of gravitational waves by a network of heterogeneous workstations, ZAPROS-LM -- a method and system for ordering multiattribute alternatives, On the structure of graphs with few \(P_4\)s, Simple planar graph partition into three forests, The heap-mergesort, Group centre and group median of a tree, Generating hard and diverse test sets for NP-hard graph problems, A self-stabilizing algorithm for detecting fundamental cycles in a graph, A characterization of Markov equivalence for directed cyclic graphs, Matrix multiplication for finite algebraic systems, Algorithms for weakly triangulated graphs
