scientific article; zbMATH DE number 3558962
From MaRDI portal
zbMath0358.68059MaRDI QIDQ4130999
Publication date: 1976
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99) Graph theory (05Cxx)
Related Items
A hybrid genetic algorithm for the three-index assignment problem, An introduction to parallelism in combinatorial optimization, Randomized algorithms in combinatorial optimization: A survey, Scaling algorithms for network problems, Grouping of parts and components in flexible manufacturing systems, On the existence of weak greedy matching heuristics, Schedule-induced posets, An algorithm for shortest-path motion in three dimensions, Improving the Hungarian assignment algorithm, A Lagrangean relaxation method for the constrained assignment problem, On some complexity properties of N-free posets and posets with bounded decomposition diameter, Most and least uniform spanning trees, Representability in mixed integer programming. I: Characterization results, On local convexity in graphs, Algorithms for finding k-best perfect matchings, Steiner problem in Halin networks, An out-of-kilter method for submodular flows, Parallel nested dissection for path algebra computations, Primal-dual algorithms for the assignment problem, A linear-time algorithm for finding a minimum spanning pseudoforest, Scheduling jobs with fixed start and end times, Fractional matchings and the Edmonds-Gallai theorem, The cost-to-time ratio problem for large or infinite graphs, Necessary and sufficient conditions of optimality for some classical scheduling problems, On a scheduling problem where a job can be executed only by a limited number of processors, Minimum deviation problems, On common edges in optimal solutions to traveling salesman and other optimization problems, The complexity of parallel search, Fixed interval scheduling: models, applications, computational complexity and algorithms, Some applications of doubly stochastic matrices, A computational study of efficient shortest path algorithms, Incremental assignment problem, Acyclic k-connected subgraphs for distributed alternate routing in communications networks, Boundary labeling: Models and efficient algorithms for rectangular maps, An algorithm for the detection and construction of Monge sequences, Traffic assignment in communication satellites, Subspaces with well-scaled frames, A generalized Hungarian method for solving minimum weight perfect matching problems with algebraic objective, Shortest path and maximum flow problems in networks with additive losses and gains, Relay placement for fault tolerance in wireless networks in higher dimensions, Multistable selection equations of pattern formation type in the case of inhomogeneous growth rates: With applications to two-dimensional assignment problems, A survey of results for sequencing problems with controllable processing times, Decomposing a relation into a tree of binary relations, The traveling salesman problem with flexible coloring, On the structure of the \(h\)-vector of a paving matroid, k-sum optimization problems, On the continuous working problem, Applying the pilot method to improve VNS and GRASP metaheuristics for the design of SDH/WDM networks, A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem, The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate, On finding optimal polytrees, A cost-scaling algorithm for \(0-1\) submodular flows, On complexity of special maximum matchings constructing, Poset matching---a distributive analog of independent matching, Two strongly polynomial cut cancelling algorithms for minimum cost network flow, The generic canonical form of a regular structured matrix pencil, A warm-start dual simplex solution algorithm for the minimum flow networks with postoptimality analyses, On the approximability of minmax (regret) network optimization problems, Approximating \(k\)-spanner problems for \(k>2\), A combinatoric interpretation of dual variables for weighted matching and \(f\)-factors, Network flow interdiction on planar graphs, Ordered vertex removal and subgraph problems, Capacitated procurement planning with price-sensitive demand and general concave-revenue functions, The shortest path problem with forbidden paths, Worst case analysis of a greedy algorithm for graph thickness, Preemptive scheduling on uniform machines to minimize mean flow time, Heuristically guided algorithm for k-parity matroid problems, An algorithm for ranking paths that may contain cycles, On dual solutions of the linear assignment problem, Structure and dimension of the eigenspace of a concave Monge matrix, Maximum weight bipartite matching in matrix multiplication time, Choosing robust solutions in discrete optimization problems with fuzzy costs, Some methods for evaluating the optimality of elements in matroids with ill-known weights, A note on the single machine scheduling to minimize the number of tardy jobs with deadlines, Hybridizing exact methods and metaheuristics: a taxonomy, Minmax regret approach and optimality evaluation in combinatorial optimization problems with interval and fuzzy weights, Computing latest starting times of activities in interval-valued networks with minimal time lags, Two flow network simplification algorithms, Network production-location problems under price uncertainty, Transmission facility planning in telecommunications networks: A heuristic approach, A parametric algorithm for convex cost network flow and related problems, Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem, On a multicriteria shortest path problem, Unions of oriented matroids, On finding the K best cuts in a network, Optimal matchings in posets, A multi-level bottleneck assignment approach to the bus drivers' rostering problem, On a special class of bicriterion path problems, Matroid optimization with the interleaving of two ordered sets, A simple version of Karzanov's blocking flow algorithm, An out-of-kilter method for the algebraic circulation problem, The matroidal knapsack: A class of (often) well-solvable problems, Boolean techniques for matroidal decomposition of independence systems and applications to graphs, On the regularity of matrices in min algebra, Equivalence between the minimum covering problem and the maximum matching problem, A heuristic approach to the bus driver scheduling problem, The multiperiod assignment problem: A multicommodity network flow model and specialized branch and bound algorithm, A linear time algorithm for the maximum capacity path problem, On negative cycles in mixed graphs, A lower bound to the complexity of Euclidean and rectilinear matching algorithms, Characterizations of consistent marked graphs, The construction of stable project baseline schedules, Bounded MSC communication, Determination of the best main serial chain in nonserial dynamic programming networks, Sensitivity analysis for symmetric 2-peripatetic salesman problems, A network-based model for transporting extremely hazardous materials, Efficient transitive closure of sparse matrices over closed semirings, Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context, Isomorphism of chordal (6, 3) graphs, On component-size bounded Steiner trees, Extremal eigenproblem for bivalent matrices, Free multiflows in bidirected and skew-symmetric graphs, Constructing the minimization diagram of a two-parameter problem, Matroid optimization with generalized constraints, Partial inverse assignment problems under \(l_{1}\) norm, Heterogeneous-criteria scheduling: Minimizing weighted number of tardy jobs and weighted completion time, A fixed-parameter tractable algorithm for matrix domination, Generalizing the all-pairs min cut problem, Constrained matroidal bottleneck problems, Cardinality-restricted chains and antichains in partially ordered sets, Ordinal algorithms for parallel machine scheduling, Single machine scheduling to minimize the number of early and tardy jobs, Dynamics of global remittances: a graph-based analysis, All-pairs-shortest-length on strongly chordal graphs, On the isomorphism of graphs with few P4s, Directed path graph isomorphism, Solutions for subset sum problems with special digraph constraints, On the minimum monochromatic or multicolored subgraph partition problems, On cycle cones and polyhedra, Efficient computation of the oriented chromatic number of recursively defined digraphs, Outbound shipment mode considerations for integrated inventory and delivery lot-sizing decisions, Optimization with binet matrices, The partial inverse minimum spanning tree problem when weight increase is forbidden, Structure of the eigenspace of a Monge matrix in max-plus algebra, A metric for evaluating software architecture and communication models consistency, Total domination in interval graphs, Oriented coloring on recursively defined digraphs, Modeling the reentrant job shop scheduling problem with setups for metaheuristic searches, Persistency in combinatorial optimization problems on matroids, Semi-on-line scheduling with ordinal data on two uniform machines, Steiner trees and polyhedra, Fully dynamic recognition algorithm and certificate for directed cographs, On characterizations for subclasses of directed co-graphs, Heuristics for scheduling unrelated parallel machines, On the structure at infinity of a structured system, Lengths of tours and permutations on a vertex set of a convex polygon., Fast and efficient solution of path algebra problems, A natural notion of morphism for linear programming problems, A multiply constrained matroid optimization problem, A hybrid algorithm for the shortest path between two nodes in the presence of few negative arcs, Bin packing using semi-ordinal data, An extension of Christofides heuristic to the k-person travelling salesman problem, \(\ell\)-parametric eigenproblem in max-algebra, Extension of M-convexity and L-convexity to polyhedral convex functions, Efficient minimum spanning tree construction with Delaynay triangulation, Steiner's problem in double trees, A branch-and-bound procedure for the multi-mode resource-constrained project scheduling problem with minimum and maximum time lags, Complexity of finding dense subgraphs, Periodic assignment and graph colouring, An ordered independence system and its applications to scheduling problems, On the complexity of some basic problems in computational convexity. I. Containment problems, Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems, The \(k\)-cardinality assignment problem, The \(\beta\)-assignment problem in general graphs, A fast parallel algorithm to recognize P4-sparse graphs, A bound for the symmetric travelling salesman problem through matroid formulation, Activity nets: A guided tour through some recent developments, Distribution of gas cylinders, On the structure of graphs with few \(P_4\)s, The greedy algorithm for partially ordered sets, Ranking arborescences in O(Km log n) time, Negation can be exponentially powerful, On the complexity of computing bilinear forms with \(\{0,1\}\) constants, Scalar aggregation in inconsistent databases., On the measurement of complexity in activity networks, Decomposable multi-parameter matroid optimization problems., An O(m log D) algorithm for shortest paths, Complexity of spanning tree problems: Part I, On \(O(n^2)\) heuristic algorithm for the directed Steiner minimal tree problem, Optimal planning of network structures within an exchange area, Linear-time approximation algorithms for finding the minimum-weight perfect matching on a plane, Heuristics and their design: A survey, Complement reducible graphs, A new algorithm for reoptimizing shortest paths when the arc costs change, A new algorithm to find the shortest paths between all pairs of nodes, Linear programming the global approach, A linear algorithm to determine minimal spanning forests in chain graphs, The global theory of paths in networks. I: Definitions, examples and limits, Parallel machine scheduling of machine-dependent jobs with unit-length., On search over rationals, A noniterative multiproduct multiperiod production planning method, The principal lattice of partitions of a submodular function, On the directed hop-constrained shortest path problem, Monotonizing linear programs with up to two nonzeroes per column, Orientation of signed graphs, On matroids and hierarchical graphs, On a unique tree representation for \(P_ 4\)-extendible graphs, A tree representation for \(P_ 4\)-sparse graphs, An \(O(n^ 2)\) algorithm for the maximum cycle mean of an \(n\times n\) bivalent matrix, On the tree packing problem, Job lateness in a two-machine flowshop with setup times separated, On-line computation of minimal and maximal length paths, A matching algorithm for regular bipartite graphs, A short proof that matching matroids are transversal, Dynamic programming with convexity, concavity and sparsity, Random pseudo-polynomial algorithms for some combinatorial programming problems, On the minimax approximation in the class of the univariate piecewise constant functions, A multicriteria Pareto-optimal path algorithm, Steiner trees with \(n\) terminals among \(n+1\) nodes, A pseudo-polynomial algorithm for detecting minimum weighted length paths in a network, An approximation algorithm for the general routing problem, Lot-sizing polyhedra with a cardinality constraint, Matching theory -- a sampler: From Dénes König to the present, Cost-performance tradeoffs for interconnection networks, Paroids: A canonical format for combinatorial optimization, Approximating the permanent of graphs with large factors, Processor optimization for flow graphs, An algorithm for finding the \(k\) quickest paths in a network, The complexity of finding arborescences in hypergraphs, The interconnection problem, Capacity expansion of fiber optic networks with WDM systems: problem formulation and comparative analysis, Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data, Polynomial approximation algorithms with performance guarantees: an introduction-by-example, The Min-Max Spanning Tree Problem and some extensions, A characterization of the minimum cycle mean in a digraph, Approximating matchings in parallel, Testing the necklace condition for shortest tours and optimal factors in the plane, New formulations and solution procedures for the hop constrained network design problem., An \(O(n^{2}\)) algorithm for maximum cycle mean of Monge matrices in max-algebra., The base-matroid and inverse combinatorial optimization problems., Competitive location, production, and market selection, Special parity of perfect matchings in bipartite graphs, ``Global graph problems tend to be intractable, Future paths for integer programming and links to artificial intelligence, Bottleneck assignment problems under categorization, Single machine scheduling with batch deliveries, Low earth orbit satellite based communication systems -- research opportunities, Some recent results in combinatorial approaches to dynamical systems, A new approach to the study of the ground-state properties of 2D Ising spin glass, The \(\beta\)-assignment problems, Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems, Forward-reserve allocation in a warehouse with unit-load replenishments, A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence relations, Minmax regret solutions for minimax optimization problems with uncertainty, An algorithm for the ranking of shortest paths, Algorithms for preemptive scheduling of different classes of processors to do jobs with fixed times, Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations, On the maximum capacity augmentation algorithm for the maximum flow problem, Finding all the negative cycles in a directed graph, Unified approach to fuzzy graph problems, Complexity results for the \(p\)-median problem with mutual communication, Partition-distance: A problem and class of perfect graphs arising in clustering, Parallel algorithms for the assignment and minimum-cost flow problems, Ordinal algorithms for parallel machine scheduling with nonsimultaneous machine available times, Tabu search for resource-constrained scheduling, Covering a poset by interval orders, On the complexity of the dual method for maximum balanced flows
