scientific article; zbMATH DE number 3449757

Jeffrey D. Ullman, John E. Hopcrofts, A. V. Aho

Publication date: 1969

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10)

Related Items (only showing first 100 items - show all)

Length-bounded disjoint paths in planar graphs ⋮ More efficient PAC-learning of DNF with membership queries under the uniform distribution ⋮ 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 ⋮ The complexity of assigning genotypes to people in a pedigree consistently ⋮ Algorithms for weakly triangulated graphs ⋮ Efficient computation of an isotonic median regression ⋮ Single step searching in weighted block graphs ⋮ Cost-optimal parallel algorithms for constructing B-trees ⋮ A note of an \(O(n^{3}/\log n)\) time algorithm for all pairs shortest paths ⋮ On the range maximum-sum segment query problem ⋮ Deadlocks and traps in Petri nets as Horn-satisfiability solutions and some related polynomially solvable problems ⋮ 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 ⋮ Solving a vehicle routing problem by balancing the vehicles time utilization. ⋮ Algorithmic approach to counting of certain types \(m\)-ary partitions. ⋮ A modular reduction for GCD computation. ⋮ Computing the sign or the value of the determinant of an integer matrix, a complexity survey. ⋮ A note on computing graph closures ⋮ Dynamic programming on a functional memory computer ⋮ The obnoxious center problem on weighted cactus graphs. ⋮ Skolem functions of arithmetical sentences. ⋮ Graph isomorphism and identification matrices: Sequential algorithms ⋮ A survey on the continuous nonlinear resource allocation problem ⋮ Solving hyperbolic PDE's on hypercubes ⋮ Counting truth assignments of formulas of bounded tree-width or clique-width ⋮ A survey of computational complexity results in systems and control ⋮ AVL trees with relaxed balance ⋮ Reoptimization in Lagrangian methods for the \(0\)-\(1\) quadratic knapsack problem ⋮ An efficient algorithm for minimizing earliness, tardiness, and due-date costs for equal-sized jobs ⋮ Efficient parallel factorization and solution of structured and unstructured linear systems ⋮ The determinant of a unicyclic graph's neighborhood matrix ⋮ Structuring product development processes ⋮ Fast connected-component labeling ⋮ Fully dynamic all pairs shortest paths with real edge weights ⋮ On the severity of Braess's paradox: designing networks for selfish users is hard ⋮ An efficient representation for implementing finite state machines based on the double-array ⋮ The computational complexity of the criticality problems in a network with interval activity times ⋮ Boolean expression diagrams ⋮ World-championship-caliber Scrabble* ⋮ On the relationship between model-based debugging and program slicing ⋮ 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 ⋮ Resolution deduction to detect satisfiability for another class including non-Horn sentences in propositional logic ⋮ Fast and efficient parallel evaluation of the zeros of a polynomial having only real zeros ⋮ On efficient parallel computations of costs of paths on a grid graph ⋮ On the orderability problem for PLA folding ⋮ Data structures in real-time environment ⋮ The heap-mergesort ⋮ Fuzzy linear systems ⋮ On the transformation semigroups of finite automata ⋮ A linear algorithm for the domination number of a series-parallel graph ⋮ Scheduling unit-time tasks with integer release times and deadlines ⋮ Polynomial complete problems in automata theory ⋮ Insertion-safeness in balanced trees ⋮ Solving covering problems and the uncapacitated plant location problem on trees ⋮ On the NP-hardness of edge-deletion and -contraction problems ⋮ Time complexity of loop-free two-way pushdown automata ⋮ A simulation result for two-way pushdown automata ⋮ A data structure for dynamic range queries ⋮ An approximation algorithm for the Hamiltonian walk problem on maximal planar graphs ⋮ Union and split operations on dynamic trapezoidal maps ⋮ Incremental convex planarity testing ⋮ A new variant of a vehicle routing problem: Lower and upper bounds ⋮ Theory of 2-3 heaps ⋮ Exact computation of Steiner minimal trees in the plane ⋮ Scaling algorithms for network problems ⋮ Exact methods for the knapsack problem and its generalizations ⋮ Irreducibility of multivariate polynomials ⋮ Algorithm partition and parallel recognition of general context-free languages using fixed-size VLSI architecture ⋮ Jebelean-Weber's algorithm without spurious factors ⋮ Simple DFS on the complement of a graph and on partially complemented digraphs ⋮ Domination analysis for minimum multiprocessor scheduling ⋮ Algorithmic aspects for multiple-choice hardware/software partitioning ⋮ On recognition of threshold tolerance graphs and their complements ⋮ Recognizing Cartesian products in linear time ⋮ A clustering algorithm based on maximal \(\varTheta\)-distant subtrees ⋮ A class of algorithms which require nonlinear time to maintain disjoint sets ⋮ Cut scheduling in the apparel industry ⋮ Algorithms for the edge-width of an embedded graph ⋮ Efficient inclusion testing for simple classes of unambiguous \(\omega \)-automata ⋮ On arithmetical algorithms over finite fields ⋮ Parallelism and fast solution of linear systems ⋮ q-hook length formulas for forests ⋮ The weighted perfect domination problem ⋮ Edge-disjoint paths in a grid bounded by two nested rectangles ⋮ A faster algorithm for the maximum weighted tardiness problem ⋮ On two dual classes of planar graphs ⋮ Computing the longest diagonal of a simple polygon ⋮ Hidden surface removal for rectangles ⋮ Computational complexity of sentences over fields ⋮ Time-varying Reeb graphs for continuous space-time data

This page was built for publication: