scientific article
From MaRDI portal
Publication:3707420
zbMath0584.68077MaRDI QIDQ3707420
Publication date: 1983
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
analysis of algorithmsmatchingsshortest pathsnetwork flowssearch treesnetwork optimizationcombinatorial algorithmsminimum spanning treesheapsdisjoint setslinking and cutting trees
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
Latency, capacity, and distributed minimum spanning trees, Balancing problems in acyclic networks, Matroids arising from electrical networks, Trans-dichotomous algorithms for minimum spanning trees and shortest paths, Faster isometric embedding in products of complete graphs, Data structures for two-edge connectivity in planar graphs, The hybrid spanning tree problem, Halfspace learning, linear programming, and nonmalicious distributions, Improved complexity bound for the maximum cardinality bottleneck bipartite matching problem, A constant update time finger search tree, Planarity testing in parallel, \(k\)-connectivity and decomposition of graphs into forests, Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors, New primal and dual matching heuristics, On minimum and maximum spanning trees of linearly moving points, An iterative approach to verification of real-time systems, Dynamic expression trees, On the \(k\)-coloring of intervals, The arborescence-realization problem, Weighted graph based ordering techniques for preconditioned conjugate gradient methods, All-pairs shortest paths and the essential subgraph, Combinatorial relaxation algorithm for the maximum degree of subdeterminants: Computing Smith-McMillan form at infinity and structural indices in Kronecker form, On the computational complexity of dynamic graph problems, A note on finding compact sets in graphs represented by an adjacency list, A simpler minimum spanning tree verification algorithm, Question-asking strategies for Horn clause systems, On spanning 2-trees in a graph, Vertex heaviest paths and cycles in quasi-transitive digraphs, Alternating cycles and paths in edge-coloured multigraphs: A survey, A robust and scalable algorithm for the Steiner problem in graphs, Inferring most likely queue length from transactional data, Mixed graph colorings, A constrained edit distance between unordered labeled trees, Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm, Shortest paths algorithms: Theory and experimental evaluation, A linear time algorithm for maximum matchings in convex, bipartite graphs, A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment, An SE-tree-based prime implicant generation algorithm, Lower bounds for the quadratic semi-assignment problem, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, Kinetic Euclidean minimum spanning tree in the plane, The weak-heap data structure: variants and applications, Approximation algorithms for constructing spanning \(K\)-trees using stock pieces of bounded length, Improved algorithms for even factors and square-free simple \(b\)-matchings, Optimal discrete Morse functions for 2-manifolds, Improved bounds for finger search on a RAM, Distributed verification of minimum spanning trees, An optimal PRAM algorithm for a spanning tree on trapezoid graphs., Efficient algorithm for finding ground-states in the random field Ising model with an external field, Constant-time local computation algorithms, Off-line dynamic maintenance of the width of a planar point set, Dynamic programming with convexity, concavity and sparsity, On the computational behavior of a polynomial-time network flow algorithm, A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems, Amortized analysis of some disk scheduling algorithms: SSTF, SCAN, and \(N\)-step SCAN, On sparse spanners of weighted graphs, A new Karzanov-type \(O(n^ 3)\) max-flow algorithm, A pseudo-polynomial algorithm for detecting minimum weighted length paths in a network, A linear time algorithm for graph partition problems, Parallel methods for visibility and shortest-path problems in simple polygons, Efficient methods for multiple sequence alignment with guaranteed error bounds, Exact algorithms for OWA-optimization in multiobjective spanning tree problems, The most vital edges in the minimum spanning tree problem, I/O- and CPU-optimal recognition of strongly connected components, An optimal algorithm for the period of a strongly connected digraph, An algorithm for insertion of idle time in the single-machine scheduling problem with convex cost functions, Planar minimally rigid graphs and pseudo-triangulations, An analogue of Hoffman's circulation conditions for max-balanced flows, The problem of the optimal biobjective spanning tree, The one-to-one shortest-path problem: An empirical analysis with the two- tree Dijkstra algorithm, Approximating matchings in parallel, Scheduling crackdowns on illicit drug markets, A heuristic for blocking flow algorithms, Computing the binding number of a graph, Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree, A nearly optimal deterministic parallel Voronoi diagram algorithm, Computing with pipelined block transfer, K-center and K-median problems in graded distances, Computational investigations of maximum flow algorithms, Approximation algorithms for the shortest common superstring problem, Approximation algorithms for some optimum communication spanning tree problems, An algorithm for geometric minimum spanning trees requiring nearly linear expected time, An implementation of Karmarkar's algorithm for linear programming, Approximate minimum weight matching on points in k-dimensional space, Minimal length test vectors for multiple-fault detection, A data structure for dynamic trees, Coloring graphs with no \(\text{odd-}K_4\), Alternating cycles and trails in \(2\)-edge-coloured complete multigraphs, A note on practical construction of maximum bandwidth paths., Incremental convex planarity testing, Manipulating multiple stacks with ordered-heap, The Steiner problem in distributed computing systems, Finding paths in graphs avoiding forbidden transitions, Port partitioning and dynamic queueing for IP forwarding, Efficient algorithms for minimum-cost flow problems with piecewise-linear convex costs, A faster parametric minimum-cut algorithm, Network flow and 2-satisfiability, On lookahead in the list update problem, Finding the closed partition of a planar graph, Speeding up dynamic transitive closure for bounded degree graphs, A dual approach for solving the combined distribution and assignment problem with link capacity constraints, Scaling algorithms for network problems, Experimentation in optimization, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, A stronger lower bound on parametric minimum spanning trees, The pairing heap: A new form of self-adjusting heap, Shortest paths in Euclidean graphs, An augmenting path algorithm for linear matroid parity, Gallai-Edmonds decomposition as a pruning technique, Activity optimization games with complementarity, Multiple phase neighborhood search---GRASP based on Lagrangean relaxation, random backtracking Lin-Kernighan and path relinking for the TSP, A linear-time algorithm for finding a minimum spanning pseudoforest, Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons, Incremental evaluation for attribute grammars with unrestricted movement between tree modifications, Communication-efficient parallel algorithms for distributed random-access machines, The general maximum matching algorithm of Micali and Vazirani, On common edges in optimal solutions to traveling salesman and other optimization problems, A sequential dual simplex algorithm for the linear assignment problem, An application of discrete mathematics in the design of an open pit mine, The generation of random permutations on the fly, On the efficiency of maximum-flow algorithms on networks with small integer capacities, Minimum spanning trees in networks with varying edge weights, A computational study of efficient shortest path algorithms, An efficient algorithm for the Brownian dynamics simulation of aggregation, Making data structures persistent, Fast heuristic algorithms for rectilinear Steiner trees, The parallel complexity of finding a blocking flow in a 3-layer network, Algorithms for multicommodity flows in planar graphs, Tight bounds for distributed minimum-weight spanning tree verification, A Bayesian approach to relevance in game playing, The planar multiterminal cut problem, Finding dominators via disjoint set union, Shortest path and maximum flow problems in networks with additive losses and gains, Fréchet distance with speed limits, \(n\)-step cycle inequalities: facets for continuous multi-mixing set and strong cuts for multi-module capacitated lot-sizing problem, The disjoint paths problem in quadratic time, A kinetic triangulation scheme for moving points in the plane, Finding the shortest paths by node combination, A data structure useful for finding Hamiltonian cycles, Dynamic maintenance of planar digraphs, with applications, Hidden surface removal for rectangles, Solving k-shortest and constrained shortest path problems efficiently, Reconstructing shortest paths, The saga of minimum spanning trees, An efficient algorithm for the minimum capacity cut problem, Computing the arrangement of circles on a sphere, with applications in structural biology, An efficient scaling algorithm for the minimum weight bibranching problem, Small-dimensional linear programming and convex hulls made easy, Use of dynamic trees in a network simplex algorithm for the maximum flow problem, A pointer-free data structure for merging heaps and min-max heaps, Routing in VLSI-layout, Steiner minimal trees for three points with one convex polygonal obstacle, Parallel priority queues, Las Vegas RNC algorithms for unary weighted perfect matching and \(T\)-join problems, On an instance of the inverse shortest paths problem, Finding minimum-cost flows by double scaling, Shortest path algorithms: A computational study with the C programming language, Two methods for the generation of chordal graphs, Efficient algorithms for machine scheduling problems with earliness and tardiness penalties, On-line computation of minimal and maximal length paths, Expanding neighborhood search-GRASP for the probabilistic traveling salesman problem, Three priority queue applications revisited, Stability number and chromatic number of tolerance graphs, Maintaining bridge-connected and biconnected components on-line, Forests, frames, and games: Algorithms for matroid sums and applications, A fast algorithm for the generalized parametric minimum cut problem and applications, How to find Steiner minimal trees in Euclidean \(d\)-space, An O(log n) parallel algorithm for constructing a spanning tree on permutation graphs, The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate, Filling gaps in the boundary of a polyhedron, Geometric pattern matching under Euclidean motion, Hybrid Bellman-Ford-Dijkstra algorithm, On the SPANNING \(k\)-TREE problem, A genuinely polynomial primal simplex algorithm for the assignment problem, Dynamic reachability in planar digraphs with one source and one sink, Some comments on building heaps in parallel, Position heaps: a simple and dynamic text indexing data structure, Selected topics on assignment problems, The extended global cardinality constraint: an empirical survey, An implicit representation of chordal comparability graphs in linear time, Efficient authenticated data structures for graph connectivity and geometric search problems, On sorting, heaps, and minimum spanning trees, Computing large matchings in planar graphs with fixed minimum degree, Low-energy excitations in the three-dimensional random-field Ising model, Computing pseudotriangulations via branched coverings, An algorithmic study of switch graphs, Some approximation algorithms for the clique partition problem in weighted interval graphs, A constrained edit distance algorithm between semi-ordered trees, A new constrained edit distance between quotiented ordered trees, Hopf-algebraic structure of families of trees, An extension of labeling techniques for finding shortest path trees, Rank-two 5d SCFTs from M-theory at isolated toric singularities: a systematic study, An 0(n log n) algorithm for the convex bipartite matching problem, Higher-dimensional Voronoi diagrams in linear expected time, General algorithms for the address calculation of lexicographically ordered tuples, The maximum flow problem: A max-preflow approach, Maximizing profits of routing in WDM networks, Sequential access in splay trees takes linear time, A sausage heuristic for Steiner minimal trees in three-dimensional Euclidean space, A multiperiod min-sum arborescence problem, A New Similarity Measure and Its Use in Determining the Number of Clusters in a Multivariate Data Set, Optimal parallel verification of minimum spanning trees in logarithmic time, The recognition of union trees, Ray shooting on triangles in 3-space, A heuristic improvement of the Bellman-Ford algorithm, A distributed exact algorithm for the multiple resource constrained sequencing problem, Hollow Heaps, Preconditioning Linear Least-Squares Problems by Identifying a Basis Matrix, Recognizing \(d\)-interval graphs and \(d\)-track interval graphs, Generating sparse spanners for weighted graphs, Fully dynamic 2-edge-connectivity in planar graphs, Practical sequential bounds for approximating two-terminal reliability, Paths and trails in edge-colored graphs, Optimal per-edge processing times in the semi-streaming model, Strongly adaptive token distribution, A Dynamic Algorithm for Reachability Games Played on Trees, A heuristic for decomposing traffic matrices in TDMA satellite communication, Unnamed Item, On packing and coloring hyperedges in a cycle, On random cartesian trees, AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗, A PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH FIRST SEARCH, Amortized Computational Complexity, On the time and space complexity of computation using write-once memory or is pen really much worse than pencil?, A class of bounded approximation algorithms for graph partitioning, Choquet-based optimisation in multiobjective shortest path and spanning tree problems, Note: Small integral flows need only sparse networks, Families of solutions of nonlinear pseudo-boolean relations, Target control and expandable target control of complex networks, Multiple alignment of biological sequences with gap flexibility, Proof-labeling schemes: broadcast, unicast and in between, Efficient algorithms for minimum range cut problems, Efficient breakout routing in printed circuit boards, Unnamed Item, An Application of Generalized Tree Pebbling to Sparse Matrix Factorization, Stochastic global optimization methods part II: Multi level methods, Maximum series-parallel subgraph, Layered working-set trees, Principles of electricity and economics in fluid dynamics, Three problems about simple polygons, Classifying the computational complexity of problems, Relation-algebraic verification of Borůvka's minimum spanning tree algorithm, Incremental Algorithms to Update Visibility Polygons, On some matching problems arising in vehicle scheduling models, Computingk-shortest path lengths in euclidean networks, Unnamed Item, Efficient data race detection for async-finish parallelism, The complexity of minimum cut and maximum flow problems in an acyclic network, Large neighborhood improvements for solving car sequencing problems, Unnamed Item, Designing a minimal spanning tree network subject to a budget constraint, Towards a real time algorithm for parameterized longest common prefix computation, A New Heuristic for Minimum Weight Triangulation, A self-stabilizing algorithm for the maximum flow problem, The shortest path with at most / nodes in each of the series/parallel clusters, State-of-the-Art Sparse Direct Solvers, Dynamic Algorithms for Visibility Polygons in Simple Polygons, Spanning-Tree Games., A zero-space algorithm for negative cost cycle detection in networks, Classification of integral lattices with large class number, A comparison of phase and nonphase network flow algorithms, An optimal-time algorithm for shortest paths on a convex polytope in three dimensions, Unnamed Item, Fast ping-pong arbitration for input-output queued packet switches, Oriented star packings, An algorithm for ranking assignments using reoptimization, A quick method for finding shortest pairs of disjoint paths, Un nuevo resultado sobre la complejidad del problema delP-centro, Path problems in generalized stars, complete graphs, and brick wall graphs, Expanding neighborhood GRASP for the traveling salesman problem, How much can taxes help selfish routing?, On the severity of Braess's paradox: designing networks for selfish users is hard, Algoritmo de programação de máquinas individuais com penalidades distintas de adiantamento e atraso, Heuristic shortest path algorithms for transportation applications: state of the art, On the complexity of resilient network design, A simpler minimum spanning tree verification algorithm, Combinatorial auctions with decreasing marginal utilities, Unnamed Item, Faster Algorithms for Semi-Matching Problems, Packing paths in digraphs, Dynamic interpolation search revisited, Multiple choice tries and distributed hash tables, Contracted Suffix Trees: A Simple and Dynamic Text Indexing Data Structure, Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, Rotation Distance, Triangulations, and Hyperbolic Geometry, Properly Coloured Cycles and Paths: Results and Open Problems, Finding the k Shortest Paths, Clustering, classification and image segmentation on the grid, Rectilinear paths among rectilinear obstacles, Comparative study and proof of single-pass connected components algorithms, A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs, SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS, On graph problems in a semi-streaming model, Scheduling on a batch processing machine with split compatibility graphs, THE MINIMUM SPANNING TREE PROBLEM: Jarník's solution in historical and present context, A comprehensive simplex-like algorithm for network optimization and perturbation analysis, Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time, Fully dynamic recognition of proper circular-arc graphs, Suffix trays and suffix trists: structures for faster text indexing, Shortest Path and Maximum Flow Problems in Networks with Additive Losses and Gains, Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems, Hitting Selected (Odd) Cycles, Characterization of random walks on space of unordered trees using efficient metric simulation, Optimal parallel shortest paths in small treewidth digraphs, Steiner problems on directed acyclic graphs, On-line graph algorithms for incremental compilation, A Wait-free Queue with Polylogarithmic Step Complexity, Simpler and Incremental Consistency Checking and Arc Consistency Filtering Algorithms for the Weighted Spanning Tree Constraint, Dynamic Matching Algorithms in Practice, A stronger lower bound on parametric minimum spanning trees, Minimum dominating sets of intervals on lines, Approximating latin square extensions, An algorithm for finding the first excited state in the random-field Ising model, Minimum-weight spanning tree algorithms. A survey and empirical study, Binding-time analysis for both static and dynamic expressions, Parallel algorithms for red--black trees, On the Bahncard problem, The price of anarchy is independent of the network topology, A linear-time algorithm for symmetric convex drawings of internally triconnected plane graphs, Two strikes against perfect phylogeny, Paths and Trails in Edge-Colored Graphs, Relaxing the irrevocability requirement for online graph algorithms, Inequality-sum: a global constraint capturing the objective function, A Scalable Inclusion Constraint Solver Using Unification, Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs, Fast Augmenting Paths by Random Sampling from Residual Graphs, Random Access to Grammar-Compressed Strings and Trees, Competitive Online Search Trees on Trees, Parametric Shortest-Path Algorithms via Tropical Geometry
