scientific article

Publication date: 1976

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

computational complexity integer programming network programming combinatorial optimization matroids network flow algorithms matroid intersection algorithm polynomially bounded algorithms augmenting paths matroid greedy algorithm out-of-kilter algorithm bipartite and nonbipartite networks Np- hard problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming (90-01) Combinatorial aspects of matroids and geometric lattices (05B35)

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

Maximal dynamic polymatroid flows and applications ⋮ Experimental evaluation of a local search approximation algorithm for the multiway cut problem ⋮ Hierarchical \(b\)-matching ⋮ Euclidean maximum matchings in the plane -- local to global ⋮ Branch-and-price algorithm for the resilient multi-level hop-constrained network design ⋮ Optimal relay node placement in delay constrained wireless sensor network design ⋮ A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem ⋮ Complexity results for storage loading problems with stacking constraints ⋮ Community detection by modularity maximization using GRASP with path relinking ⋮ Fuzzy shortest path problem with finite fuzzy quantities ⋮ The theory and practice of distance geometry ⋮ Scheduling machine-dependent jobs to minimize lateness on machines with identical speed under availability constraints ⋮ Algorithms for the quickest path problem and the reliable quickest path problem ⋮ Optimal placement of UV-based communications relay nodes ⋮ Solution of the Liu-Layland problem via bottleneck just-in-time sequencing ⋮ Single processor scheduling with job values depending on their completion times ⋮ The weak robustness of interval matrices in max-plus algebra ⋮ NP-hardness of two edge cover generalizations with applications to control and bribery for approval voting ⋮ Parameterized and subexponential-time complexity of satisfiability problems and applications ⋮ Stability analysis in discrete optimization involving generalized addition operations ⋮ Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation ⋮ Matching based very large-scale neighborhoods for parallel machine scheduling ⋮ On flows in simple bidirected and skew-symmetric networks ⋮ Spatio-temporal multi-robot routing ⋮ A multicast routing algorithm based on searching in directed graph ⋮ Linear-code multicast on parallel architectures ⋮ Bee colony optimization for the \(p\)-center problem ⋮ Possibilistic bottleneck combinatorial optimization problems with ill-known weights ⋮ Partitioning planar graphs: a fast combinatorial approach for max-cut ⋮ Scheduling of project networks ⋮ The generalized assignment problem: Valid inequalities and facets ⋮ Partitioning multi-edge graphs ⋮ Polynomial time approximation schemes for the constrained minimum spanning tree problem ⋮ A survey of dynamic network flows ⋮ Reconstructing shortest paths ⋮ Retiming synchronous circuitry ⋮ The ``molecular traveling salesman ⋮ An algorithm for weighted fractional matroid matching ⋮ A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem ⋮ Lower bounds and modified LPT algorithm for \(k\)-partitioning problems with partition matroid constraint ⋮ A model for minimizing active processor time ⋮ An overview of channel assignment methods for multi-radio multi-channel wireless mesh networks ⋮ A column generation approach for multicast routing and wavelength assignment with delay constraints in heterogeneous WDM networks ⋮ Solving the parametric bipartite maximum flow problem in unbalanced and closure bipartite graphs ⋮ On set expansion problems and the small set expansion conjecture ⋮ The Steiner tree problem with delays: a compact formulation and reduction procedures ⋮ Phase transition on the convergence rate of parameter estimation under an Ornstein-Uhlenbeck diffusion on a tree ⋮ A new approach for solving the network problems ⋮ Greed is good: Approximating independent sets in sparse and bounded-degree graphs ⋮ George Dantzig's impact on the theory of computation ⋮ The \(k\)-path tree matroid and its applications to survivable network design ⋮ Finding Hamiltonian circuits in quasi-adjoint graphs ⋮ Bounded discrete representations of interval orders ⋮ Hierarchical decomposition of symmetric discrete systems by matroid and group theories ⋮ Approximating the tree and tour covers of a graph ⋮ On worst-case aggregation analysis for network location problems ⋮ Commitment under uncertainty: Two-stage stochastic matching problems ⋮ Complexity of the sex-equal stable marriage problem ⋮ Using combinatorial optimization in model-based trimmed clustering with cardinality constraints ⋮ Shape rectangularization problems in intensity-modulated radiation therapy ⋮ The central curve in linear programming ⋮ Semigroup identities in the monoid of two-by-two tropical matrices. ⋮ Maximum outflow in generalized flow networks ⋮ Maximum sum-of-splits clustering ⋮ Partial inverse of a monotone operator ⋮ A novel iterative shape from focus algorithm based on combinatorial optimization ⋮ Blossom V: A new implementation of a minimum cost perfect matching algorithm ⋮ Recognizing underlying sparsity in optimization ⋮ Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey ⋮ Making sparse matrices sparser: Computational results ⋮ \(k\)-partitioning problems with partition matroid constraint ⋮ Approximating the maximum clique minor and some subgraph homeomorphism problems ⋮ Structural theorems for submodular functions, polymatroids and polymatroid intersections ⋮ A polynomial algorithm for minimum quadratic cost flow problems ⋮ An extension of labeling techniques for finding shortest path trees ⋮ Persistency and matroid intersection ⋮ A note on a generalized network flow model for manufacturing process ⋮ On matroid parity and matching polytopes ⋮ Approximating the longest path length of a stochastic DAG by a normal distribution in linear time ⋮ Recent trends in combinatorial optimization ⋮ An equivalent subproblem relaxation for improving the solution of a class of transportation scheduling problems ⋮ Nowhere-zero integral flows on a bidirected graph ⋮ Optimal cycles in doubly weighted graphs and approximation of bivariate functions by univariate ones ⋮ On the number of common bases of two matroids ⋮ A matroid generalization of theorems of Lewin and Gallai ⋮ Networks and chain coverings in partial orders and their products ⋮ Applications of shortest path algorithms to matrix scalings ⋮ Worst-case choice for the stable marriage problem ⋮ Label-connected graphs and the gossip problem ⋮ Fuzzy shortest paths ⋮ Additive functions and their application to uncertain information ⋮ Chain packing in graphs ⋮ An algorithm for finding a matroid basis which maximizes the product of the weights of the elements ⋮ A dynamic programming algorithm to find all solutions in a neighborhood of the optimum ⋮ An efficient Dijkstra-like labeling method for computing shortest odd/even paths ⋮ Computational experience with a polynomial-time dual simplex algorithm for the transportation problem ⋮ Algorithms for the minimum weight of linear codes ⋮ Fast algorithms for the undirected negative cost cycle detection problem ⋮ PTAS for densest \(k\)-subgraph in interval graphs ⋮ Combinatorics of orientation reversing polygons

This page was built for publication: