scientific article; zbMATH DE number 1102774

William R. Pulleyblank, William H. Cunningham, William Cook

Publication date: 12 January 1998

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

shortest path matching NP-completeness matroids travelling salesman multicommodity flows minimum spanning tree network simplex dual scaling integrality of polyhedra

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

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

Tractable combinatorial auctions and \(b\)-matching ⋮ Cross line and column generation for the cut covering problem in wireless networks ⋮ Extending tournament solutions ⋮ Approximation algorithms for the \(k\)-depots Hamiltonian path problem ⋮ Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem ⋮ Generalized minor inequalities for the set covering polyhedron related to circulant matrices ⋮ The mixed evacuation problem ⋮ Scheduling with few changes ⋮ Optimal and Game-Theoretic Deployment of Security Investments in Interdependent Assets ⋮ Iteratively reweighted least squares and slime mold dynamics: connection and convergence ⋮ The computational complexity of the elimination problem in generalized sports competitions ⋮ A new heuristic for detecting non-Hamiltonicity in cubic graphs ⋮ How to collect balls moving in the Euclidean plane ⋮ Total dual dyadicness and dyadic generating sets ⋮ Revisiting a cutting-plane method for perfect matchings ⋮ On dominating set polyhedra of circular interval graphs ⋮ Finding all minimum cost flows and a faster algorithm for the \(K\) best flow problem ⋮ Structure theorem and algorithm on \((1,f)\)-odd subgraph ⋮ A simple LP relaxation for the asymmetric traveling salesman problem ⋮ A bilevel programming problem with maximization of a supermodular function in the lower level ⋮ Variable neighbourhood structures for cycle location problems ⋮ Exact and heuristic approaches for the cycle hub location problem ⋮ A history of graph entropy measures ⋮ Min Sum Edge Coloring in Multigraphs Via Configuration LP ⋮ Integer-empty polytopes in the 0/1-cube with maximal Gomory-Chvàtal rank ⋮ Finding small stabilizers for unstable graphs ⋮ Optimality conditions for a bilevel matroid problem ⋮ Changing of the guards: strip cover with duty cycling ⋮ Query-competitive algorithms for cheapest set problems under uncertainty ⋮ Dominance rules in combinatorial optimization problems ⋮ Polyhedron of triangle-free simple 2-matchings in subcubic graphs ⋮ \texttt{Procrustes}: a python library to find transformations that maximize the similarity between matrices ⋮ A detailed introduction to a minimum-cost perfect matching algorithm based on linear programming ⋮ A Survey on Covering Supermodular Functions ⋮ Recent Developments in Discrete Convex Analysis ⋮ Polynomial time approximation schemes for the constrained minimum spanning tree problem ⋮ On the approximability of some degree-constrained subgraph problems ⋮ A comparison of lower bounds for the symmetric circulant traveling salesman problem ⋮ Linearly-growing reductions of Karp's 21 NP-complete problems ⋮ A comparative study of two fast phase unwrapping algorithms. ⋮ The essence of constraint propagation ⋮ Edge-disjoint odd cycles in planar graphs. ⋮ Certifying algorithms ⋮ An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem ⋮ Approximation algorithms for partially covering with edges ⋮ Monotonizing linear programs with up to two nonzeroes per column ⋮ Bounding the payment of approximate truthful mechanisms ⋮ Using critical sets to solve the maximum independent set problem ⋮ Symmetric PMC model of diagnosis, \(b\)-matchings in graphs and fault identification in \(t\)-diagnosable systems ⋮ Capacitated Vehicle Routing with Non-uniform Speeds ⋮ Minimizing task completion time with the execution set method ⋮ Metric inequalities and the network loading problem ⋮ An exact solution method for quadratic matching: the one-quadratic-term technique and generalisations ⋮ Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs ⋮ \(V\)- and \(D\)-optimal population designs for the simple linear regression model with a random intercept term ⋮ The Erdős-Hajnal conjecture for bull-free graphs ⋮ Using combinatorial optimization in model-based trimmed clustering with cardinality constraints ⋮ Characterizations of postman sets ⋮ Graph connectivity and its augmentation: Applications of MA orderings ⋮ A class of network optimization methods for planar grid generation ⋮ Determination of the candidate arc set for the asymmetric traveling salesman problem ⋮ Workweek optimization of experimental designs: exact designs for variable sampling costs ⋮ Approximation algorithms for some vehicle routing problems ⋮ On minimum power connectivity problems ⋮ A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems ⋮ On contrasting vertex contraction with relaxation-based approaches for negative cost cycle detection ⋮ Multiprocessor scheduling under precedence constraints: polyhedral results ⋮ A graph theoretic method for determining generating sets of prime ideals in quantum matrices ⋮ Alternative integer-linear-programming formulations of the Clar problem in hexagonal systems ⋮ Home service routing and appointment scheduling with stochastic service times ⋮ Facets of the independent path-matching polytope ⋮ Scheduling problems over a network of machines ⋮ Separation routine and extended formulations for the stable set problem in claw-free graphs ⋮ Stabilizing network bargaining games by blocking players ⋮ Even factors, jump systems, and discrete convexity ⋮ Generalized network design problems. ⋮ Team formation: Matching quality supply and quality demand. ⋮ Characterizing the flow equivalent trees of a network ⋮ Semi-automatically optimized calibration of internal combustion engines ⋮ Stabilizing Weighted Graphs ⋮ Fractional matching preclusion number of graphs and the perfect matching polytope ⋮ Parity and disparity subgraphs ⋮ Approximating minimum-power edge-covers and 2,3-connectivity ⋮ Reconstruction, optimization, and design of heterogeneous materials and media: basic principles, computational algorithms, and applications ⋮ Weighted coloring on planar, bipartite and split graphs: Complexity and approximation ⋮ On the maximum size of a minimal \(k\)-edge connected augmentation ⋮ Exact and approximation algorithms for weighted matroid intersection ⋮ Graphs and Algorithms in Communication Networks on Seven League Boots ⋮ A Full Description of Polytopes Related to the Index of the Lowest Nonzero Row of an Assignment Matrix ⋮ Refined cut selection for Benders decomposition: applied to network capacity expansion problems ⋮ Using a greedy random adaptative search procedure to solve the cover printing problem ⋮ Extension of M-convexity and L-convexity to polyhedral convex functions ⋮ A note on diagonally dominant matrices ⋮ Towards an efficient resolution of printing problems ⋮ Enumerating colorings, tensions and flows in cell complexes ⋮ The minimum flow cost Hamiltonian cycle problem: a comparison of formulations ⋮ Approximation algorithms for multi-parameter graph optimization problems ⋮ Majorization-constrained doubly stochastic matrices ⋮ Partition-distance: A problem and class of perfect graphs arising in clustering ⋮ Compact vs. exponential-size LP relaxations

This page was built for publication: