scientific article; zbMATH DE number 3887060

zbMATH Open0556.68002MaRDI QIDQ3219752FDOQ3219752

Authors: K. Mehlhorn 

Publication date: 1984

Title of this publication is not available (Why is that?)

Recommendations

• scientific article; zbMATH DE number 194946
• Graphs, networks and algorithms.
• scientific article; zbMATH DE number 1805583
• scientific article; zbMATH DE number 3976318
• Graphs, networks and algorithms

zbMATH Keywords

dynamic programmingmatchingnetwork flowsgraph algorithmsNP-completenessshortest pathbranch and boundmatrix multiplicationspanning treedepth first searchpath problems

Mathematics Subject Classification ID

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

Cited In (only showing first 100 items - show all)

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

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3219752)