scientific article

zbMath0556.68002MaRDI QIDQ3219752

Publication date: 1984

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

dynamic programming shortest path matching branch and bound NP-completeness spanning tree network flows graph algorithms path problems matrix multiplication depth first search

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Algorithms in computer science (68W99)

Related Items

Approximate decision algorithms for point set congruence, A general approach to avoiding two by two submatrices, A model for deadlock detection based on automata and languages theory, Sublinear merging and natural mergesort, A verification algorithm for inheritance hierarchies in object-oriented databases, Two optimal parallel algorithms on the commutation class of a word, An improved fixed-parameter algorithm for vertex cover, Refined memorization for vertex cover, Path-based depth-first search for strong and biconnected components, Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity, Optimal contiguous expression DAG evaluations, The visibility diagram: A data structure for visibility problems and motion planning, Visibility between two edges of a simple polygon, NC algorithms for dynamically solving the all pairs shortest paths problem and related problems, The Impact of Parameterized Complexity to Interdisciplinary Problem Solving, On approximation behavior of the greedy triangulation for convex polygons, The complexity of ultrametric partitions on graphs, A complete and efficient algorithm for the intersection of a general and a convex polyhedron, Generalized approximate algorithms for point set congruence, Constraint programming and graph algorithms., Lower bounds for set intersection queries, Generalised cumulative arrays in secret sharing, Secret sharing schemes with partial broadcast channels, Combinatorial algorithms for DNA sequence assembly, Theory of traces, An improved algorithm for transitive closure on acyclic digraphs, Direct graph \(k\)-partitioning with a Kernighan-Lin like heuristic, Large-scale network analysis with applications to transportation, communication and inference networks, Algorithms for dense graphs and networks on the random access computer, On the upper bound of the complexity of sorting, On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm, The complexity of embedding orders into small products of chains, State-variable planning under structural restrictions: algorithms and complexity, Computing minimum spanning forests on 1- and 2-dimensional processor arrays, On the performance of networks with multiple busses, Performance driven k-layer wiring, On a discrete optimization problem, Complexité de problèmes liés aux graphes sans circuit, Quotient geometric crossovers and redundant encodings, On-line graph algorithms for incremental compilation, Using Brouwer’s Fixed Point Theorem, Constraint bipartite vertex cover: simpler exact algorithms and implementations, Dynamic fractional cascading, Introduction to graph grammars with applications to semantic networks, A naive algorithm for feedback vertex set, A new planarity test, Visibility graphs and obstacle-avoiding shortest paths, Evolving Perfect Hash Families: A Combinatorial Viewpoint of Evolving Secret Sharing, Parametric maximal flows in generalized networks – complexity and algorithms, On the complexity of approximating the independent set problem, Counting and cutting cycles of lines and rods in space, Approximate decision algorithms for approximate congruence, Maintenance of 2- and 3-edge-connected components of graphs. I, On the calculation of transitive reduction-closure of orders, Analysis of swaps in radix selection, The complexity of coloring games on perfect graphs, Adaptive sorting: an information theoretic perspective, Some baby-step giant-step algorithms for the low hamming weight discrete logarithm problem, Competitive graph searches, The slab dividing approach to solve the Euclidean \(P\)-center problem, I/O- and CPU-optimal recognition of strongly connected components, Consensus algorithms for the generation of all maximal bicliques, NP-hardness of the stable matrix in unit interval family problem in discrete time, Unnamed Item, Lower Bounds on the Complexity of Polytope Range Searching, On families of categorial grammars of bounded value, their learnability and related complexity questions, Extending planar graph algorithms to \(K_{3,3}\)-free graphs, Improving the running time of embedded upward planarity testing, An Improved Upward Planarity Testing Algorithm and Related Applications, Least commitment in Graphplan, Notes on liveness and boundedness of extended strong asymmetric choice nets. II, Polynomial hash functions are reliable, An analogue of Hoffman's circulation conditions for max-balanced flows, Unnamed Item, Generalized Polychotomic Encoding: A Very Short Bit-Vector Encoding of Tree Hierarchies, Testing the necklace condition for shortest tours and optimal factors in the plane, Traversing graphs in a paging environment, BFS or DFS?, On the Circuit Complexity of Perfect Hashing, Optimal linear perfect hash families, On the complexity of approximating the independent set problem, An adaptation of SH heuristic to the location set covering problem, Secure frameproof codes, key distribution patterns, group testing algorithms and related structures, Computational analysis of a flexible assembly system design problem, RESILIENT LKH: SECURE MULTICAST KEY DISTRIBUTION SCHEMES, Parameterised algorithms for deletion to classes of DAGs, Acyclic Digraphs, Maintaining a topological order under edge insertions, Distributing the encryption and decryption of a block cipher, Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover, A simplified correctness proof for a well-known algorithm computing strongly connected components., Real-time properties of indirect recursive procedures, Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time, On the Euclidean two paths problem, Algorithms for transitive closure, Bit complexity of matrix products, Description of the connected components of a semialgebraic set in single exponential time