scientific article; zbMATH DE number 3643026
From MaRDI portal
Publication:3048571
augmenting pathsbipartite and nonbipartite networkscombinatorial optimizationcomputational complexityinteger programmingmatroid greedy algorithmmatroid intersection algorithmmatroidsnetwork flow algorithmsnetwork programmingNp- hard problemsout-of-kilter algorithmpolynomially bounded algorithms
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Combinatorial aspects of matroids and geometric lattices (05B35) Extremal problems in graph theory (05C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming (90-01) Deterministic network models in operations research (90B10) Integer programming (90C10) Programming involving graphs or networks (90C35)
Cited in
(only showing first 100 items - show all)- Recognizing underlying sparsity in optimization
- Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
- \(k\)-partitioning problems with partition matroid constraint
- Approximating the maximum clique minor and some subgraph homeomorphism 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
- Approximating the longest path length of a stochastic DAG by a normal distribution in linear time
- Nowhere-zero integral flows on a bidirected graph
- Networks and chain coverings in partial orders and their products
- Worst-case choice for the stable marriage problem
- 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
- Combinatorics of orientation reversing polygons
- Maximal dynamic polymatroid flows and applications
- The shortest path problem with two objective functions
- Interval orders without odd crowns are defect optimal
- Optimal precision in the presence of uncertainty
- A comment on \('NP=P?'\) and restricted partitions
- A shortest augmenting path algorithm for dense and sparse linear assignment problems
- A decomposition theory for matroids. III. Decomposition conditions
- On lattices with Möbius function \(\pm 1,0\)
- An augmenting path algorithm for linear matroid parity
- On-line updating of solutions to a class of matroid intersection problems
- On the maximum 2-1 matching
- Shortest-path problems and molecular conformation
- Order statistics and the linear assignment problem
- Undirected distances and the postman-structure of graphs
- The strong chromatic number of partial triple systems
- Approximation algorithms for weighted matching
- Two probabilistic results on rectilinear Steiner trees
- The complexity of computing best-response automata in repeated games
- A polynomial algorithm for b-matchings: An alternative approach
- Lower bounds on two-terminal network reliability
- A matroid algorithm and its application to the efficient solution of two optimization problems on graphs
- Large-scale network analysis with applications to transportation, communication and inference networks
- k-optimal solution sets for some polynomially solvable scheduling problems
- The complexity of matching with bonds
- The minimal average cost flow problem
- On maximal independent sets of vertices in claw-free graphs
- Combinatorial problems over power sets
- Matroid matching and some applications
- An algorithm for generating all maximal independent subsets of posets
- Worst case bounds for the Euclidean matching problem
- Discrete extremal problems
- An improvement in the Gavish-Shlifer algorithm for a class of transportation scheduling problems
- On factors in random graphs
- Parallel algorithms for the single source shortest path problem
- Hybrid algorithm for sequencing with bicriteria
- How to make a digraph strongly connected
- An NP-complete matching problem
- The ellipsoid method and its consequences in combinatorial optimization
- The complexity of computing metric distances between partitions
- The complexity of controlled selection
- Use of dynamic trees in a network simplex algorithm for the maximum flow problem
- Cooperative games arising from network flow problems
- Polymatroids: Construction and random algorithms
- The image of weighted combinatorial problems
- An additive bounding procedure for the asymmetric travelling salesman problem
- Finding minimum-cost flows by double scaling
- Some preemptive open shop scheduling problems with a renewable or a nonrenewable resource
- Forests, frames, and games: Algorithms for matroid sums and applications
- A fast algorithm for the generalized parametric minimum cut problem and applications
- A linear-time algorithm to construct a rectilinear Steiner minimal tree for \(k\)-extremal point sets
- Minimum spectral radius of a weighted graph
- New scaling algorithms for the assignment and minimum mean cycle problems
- A dynamic programming solution of a shortest path problem with time constraints on movement and parking
- Negative circuits for flows and submodular flows
- Path-matching problems
- The complexity of computing a best response automaton in repeated games with mixed strategies
- Solving the Euclidean bottleneck matching problem by \(k\)-relative neighborhood graphs
- Delay structure conditions for identifiability of closed loop systems
- Minimal cut cover of a graph with an application to the testing of electronic boards
- A combinatorial interior point method for network flow problems
- Crashing a maximum-weight complementary basis
- Auction algorithms for network flow problems: A tutorial introduction
- A note on the \(f\)-factor-lattice of bipartite graphs
- A hierarchical algorithm for making sparse matrices sparser
- Linear algorithms for testing the sign stability of a matrix and for finding Z-maximum matchings in acyclic graphs
- Matroids, generalized networks, and electric network synthesis
- Bimatroids and invariants
- Note on a matroid with parity condition
- Constructing disjoint paths on expander graphs
- An optimal procedure for the resource-constrained project scheduling problem with discounted cash flows and generalized precedence relations
- Approximation algorithms for minimum tree partition
- Note on inverse problem with l_ objective function
- A fast bipartite network flow algorithm for selective assembly
- The life span method -- a new variant of local search
- Combinatorial optimization models for production scheduling in automated manufacturing systems
- A dynamic programming heuristic for the \(P\)-median problem
- Fenchel-type duality for matroid valuations
- Random sampling and greedy sparsification for matroid optimization problems
- Discrete convex analysis
- An algorithm for a concave production cost network flow problem
- Constrained weighted matchings and edge coverings in graphs
- A recognition problem in converting linear programming to network flow models
- Clustering heuristics for set covering
- Modeling uncertainty in networks
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 Q3048571)
