Matching, Euler tours and the Chinese postman
From MaRDI portal
Publication:4766817
DOI10.1007/BF01580113zbMath0281.90073OpenAlexW2064284095WikidataQ55968050 ScholiaQ55968050MaRDI QIDQ4766817
Jack Edmonds, Ellis L. Johnson
Publication date: 1973
Published in: Mathematical Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01580113
Related Items
On the cycle polytope of a binary matroid, A graph approximation heuristic for the vertex cover problem on planar graphs, Families of cuts with the MFMC-property, Algorithms for the windy postman problem, Exact solutions for the construction of optimal length test sequences, General factors of graphs, A quick proof of Seymour's theorem on t-joins, Decomposition and optimization over cycles in binary matroids, Approximation algorithms for solving the constrained arc routing problem in mixed graphs, A polyhedral approach to the rural postman problem, Operations research games: A survey. (With comments and rejoinder), How to tidy up a symmetric set-system by use of uncrossing operations, Undirected distances and the postman-structure of graphs, The robot cleans up, Matrices with the Edmonds-Johnson property, A survey of models and algorithms for winter road maintenance. III: Vehicle routing and depot location for spreading, A survey of models and algorithms for winter road maintenance. IV: Vehicle routing and fleet sizing for plowing and snow disposal, The Schrijver system of odd join polyhedra, A construction for binary matroids, A hybrid heuristic procedure for the windy rural postman problem with zigzag time windows, Parameterized complexity of the \(k\)-arc Chinese postman problem, A new algorithm for the directed Chinese postman problem, Multiflows and disjoint paths of minimum total cost, Modeling and solving several classes of arc routing problems as traveling salesman problems, On the windy postman problem on Eulerian graphs, Edge disjoint Polyp Packing, Approximate solutions for the capacitated arc routing problem, Finding even subgraphs even faster, The complexity of matching with bonds, Minimum weight \((T,d)\)-joins and multi-joins, Using tabu search for solving a dynamic multi-terminal truck dispatching problem, A generalized Hungarian method for solving minimum weight perfect matching problems with algebraic objective, Traveling salesman problem with clustering, Extensions to 2-factors in bipartite graphs, Editing to Eulerian graphs, On the approximation ratio of the random Chinese postman tour for network search, Covering a graph with cycles., A heuristic algorithm based on Monte Carlo methods for the rural postman problem., A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs, A compact linear program for testing optimality of perfect matchings., On graphs which can or cannot induce Chinese Postman games with a non-empty core, Matroids and multicommodity flows, A graph-theoretical approach to a plotter pen touring problem, Euler index in uncertain graph, Rational and integral \(k\)-regular matrices., On the equivalence between some local and global Chinese postman and traveling salesman graphs, On a min--max theorem on bipartite graphs, The ellipsoid method and its consequences in combinatorial optimization, On the cut polyhedron., Tree metrics and edge-disjoint \(S\)-paths, Undirected postman problems with zigzagging option: a cutting-plane approach, Hamiltonian location problems, Search for an immobile entity on a network, Network search games with immobile hider, without a designated searcher starting point, Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs, Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus, The synchronization problem in protocol testing and its complexity, Travelling salesman problem tools for microcomputers, A deterministic tabu search algorithm for the capacitated arc routing problem, On matrices with the Edmonds-Johnson property arising from bidirected graphs, Polarity and the complexity of the shooting experiment, Tight integral duality gap in the Chinese postman problem, A cutting plane algorithm for the windy postman problem, Postman tours and cycle covers, An algorithm for min-cost edge-disjoint cycles and its applications, On cuts and matchings in planar graphs, Decomposition of a graph into two disjoint odd subgraphs, Capacitated arc routing problem with deadheading demands, My experiences as a student and researcher in OR during the 1960's and 70's, Ideal clutters, On shortest \(T\)-joins and packing \(T\)-cuts, On matrices with the Edmonds-Johnson property, On Chinese postman games where residents of each road pay the cost of their road, Complexity and approximation of the constrained forest problem, Eine gemeinsame Basis für die Theorie der Eulerschen Graphen und den Satz von Petersen, On T-joins and odd factors, On the most imbalanced orientation of a graph, Constant-factor approximations for capacitated arc routing without triangle inequality, Clustering with lower-bounded sizes. A general graph-theoretic framework, Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width, Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem, Approximation algorithm for maximum edge coloring, The maximum benefit Chinese postman problem and the maximum benefit traveling salesman problem, The mixed postman problem, Distributed testing without encountering controllability and observability problems, Proofs of two minimum circuit cover conjectures, Multiple center capacitated arc routing problems: A tabu search algorithm using capacitated trees, Heuristics for the stochastic Eulerian tour problem, Edge-contraction problems, Cost allocation in the Chinese postman problem, On the windy postman problem, Shortest coverings of graphs with cycles, Districting for salt spreading operations, The fleet size and mix problem for capacitated arc routing, The arc partitioning problem, Routeing winter gritting vehicles, On the mixed Chinese postman problem, On negative cycles in mixed graphs, On games arising from multi-depot Chinese postman problems, Fast algorithms for the undirected negative cost cycle detection problem, Adjacency on the Postman Polyhedron, Strong product of factor-critical graphs, Conservative weightings and ear-decompositions of graphs, Time-constrained Chinese postman problems, Stable honeycomb structures and temperature based trajectory optimization for wire-arc additive manufacturing, Binary group and Chinese postman polyhedra, On the Sound Covering Cycle Problem in Paired de Bruijn Graphs, Solvable cases of the \(k\)-person Chinese postman problem, Structural Parameterizations of the Mixed Chinese Postman Problem, The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs, An overview of graph covering and partitioning, A capacitated general routing problem on mixed networks, Algorithms for the Chinese postman problem on mixed networks, Patrolling a Pipeline, Hide-and-seek games on a tree to which Eulerian networks are attached, A LP-based approximation algorithm for generalized traveling salesperson path problem, An approximation algorithm for solving the heterogeneous Chinese postman problem, Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem, Better s-t-Tours by Gao Trees, Smallest (1, 2)‐eulerian weight and shortest cycle covering, Linear-Time Approximation for Maximum Weight Matching, Algorithms for the rural postman problem, Routing problems: A bibliography, Complete open-state testing of limitedly nondeterministic systems, Unnamed Item, Plane augmentation of plane graphs to meet parity constraints, A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem, Improving on best-of-many-Christofides for \(T\)-tours, The hierarchical Chinese postman problem: the slightest disorder makes it hard, yet disconnectedness is manageable, An unoriented variation on de Bruijn sequences, The restricted Chinese postman problems with penalties, Postman problems on series-parallel mixed graphs, Chinese postman games with multi-located players, A partitioning column approach for solving LED sorter manipulator path planning problems, The Capacitated Chinese Postman Problem: Lower Bounds and Solvable Cases, When the Gomory-chvátal closure coincides with the integer hull, A new view on rural postman based on Eulerian extension and matching, Trader multiflow and box-TDI systems in series-parallel graphs, An LP-based approximation algorithm for the generalized traveling salesman path problem, Approximation Algorithms for a Mixed Postman Problem with Restrictions on the Arcs, T-joins in strongly connected hypergraphs, Eulerian Circuits with No Monochromatic Transitions in Edge-Colored Digraphs with all Vertices of Outdegree Three, Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours, Search Games: A Review, Parameterized complexity of Eulerian deletion problems, Graphs inducing totally balanced and submodular Chinese postman games, Shorter tours and longer detours: uniform covers and a bit beyond, Approximating max-min weighted \(T\)-joins, An algorithm for the hierarchical Chinese postman problem, The salesman's improved tours for fundamental classes, Fully Dynamic Maximal Matching in $O(\log n)$ Update Time (Corrected Version), Cuboids, a class of clutters, Optimization with binet matrices, Approximation algorithms for some min-max postmen cover problems, A Decade of Capacitated Arc Routing, A two-stage solution approach for the directed rural postman problem with turn penalties, Expected runtimes of evolutionary algorithms for the Eulerian cycle problem, Series-parallel graphs are windy postman perfect, Finding thet-join structure of graphs, Convergence and correctness of belief propagation for the Chinese postman problem, A comparison of two different formulations for arc routing problems on mixed graphs, A tabu search algorithm for the Min-Max \(k\)-Chinese postman problem, A constraint programming approach to the Chinese postman problem with time windows, Privatized rural postman problems, Covering partially directed graphs with directed paths, Graphs with the Circuit Cover Property, The Chinese deliveryman problem, Recent results on Arc Routing Problems: An annotated bibliography, Eulerian tour algorithms for data visualization and the \({{\mathtt PairViz}}\) package, Reassembling Trees for the Traveling Salesman, Better \(s-t\)-tours by Gao trees, Collaborative delivery with energy-constrained mobile robots, A generalization of Petersen's theorem, OAR lib: an open source arc routing library, An improved upper bound on the integrality ratio for the \(s\)-\(t\)-path TSP, Idealness and 2-resistant sets, Extended formulations for radial cones, A computational study of several heuristics for the DRPP, Test Prioritization at Different Modeling Levels, The general routing polyhedron: A unifying framework, Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs, Approximation Algorithms for the Single Robot Line Coverage Problem, Fractional matroid matchings, On dual integrality in matching problems, Edge-outer graph embedding and the complexity of the DNA reporter strand problem, Four problems on graphs with excluded minors, Master polytopes for cycles of binary matroids, Parameterized Complexity of Eulerian Deletion Problems, Minimal length test vectors for multiple-fault detection, The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth, Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs, A survey of models and algorithms for winter road maintenance. I: System design for spreading and plowing, Some conditions for the existence of Euler \(H\)-trails, A GRASP heuristic for the mixed Chinese postman problem, Directed graph encoding in quantum computing supporting edge-failures, An integer programming approach for the Chinese postman problem with time-dependent travel time, The time-dependent rural postman problem: polyhedral results, Approximation algorithms for solving the heterogeneous Chinese postman problem, An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality, The aircraft maintenance base location problem, Efficient reductions of picture words, On Dyadic Fractional Packings of $T$-Joins, Reconstructing strings from substrings (Extended abstract), Continuous Patrolling Games, THE MAXIMUM WEIGHT PERFECT MATCHING PROBLEM FOR COMPLETE WEIGHTED GRAPHS IS IN PC∗†, Clean Clutters and Dyadic Fractional Packings, Eulerian location problems, On combinatorial properties of binary spaces, On matchings, T‐joins, and arc routing in road networks, Constraint relaxation for the discrete ordered median problem, A deterministic better-than-3/2 approximation algorithm for metric TSP, Arc routing problems: A review of the past, present, and future, On approximate data reduction for the Rural Postman Problem: Theory and experiments, A two-phase hybrid algorithm for the periodic rural postman problem with irregular services on mixed graphs, Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center, Approximations for the Steiner multicycle problem, Cycle-based formulations in distance geometry, Approximation algorithms for the min-max mixed rural postmen cover problem and its variants, Quantum encoding of dynamic directed graphs, Approximation algorithms for the min-max mixed rural postmen cover problem and its variants, The Tube Challenge, Unnamed Item, Minimum $T$-Joins and Signed-Circuit Covering, Improving a constructive heuristic for the general routing problem, Fast upper and lower bounds for a large‐scale real‐world arc routing problem, The single robot line coverage problem: Theory, algorithms, and experiments, Approximation algorithms for the restricted \(k\)-Chinese postman problems with penalties, Unnamed Item, Unnamed Item, Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems, Extended formulations in combinatorial optimization, Approximate solutions for the maximum benefit chinese postman problem, Unnamed Item, Extended formulations in combinatorial optimization, Optimal control of plotting and drilling machines: A case study, A new integer programming formulation of the graphical traveling salesman problem, A new integer programming formulation of the graphical traveling salesman problem, Modular circulation and applications to traffic management, Unnamed Item, On Four Problems in Graph Theory, An Approximation Algorithm for Fully Planar Edge-Disjoint Paths, Resistant Sets in the Unit Hypercube, The Robot Cleans Up, Fully Dynamic Maximal Matching in $O(\log n)$ Update Time
Cites Work
- Networks and vehicle routing for municipal waste collection
- On the surface duality of linear graphs
- Paths, Trees, and Flowers
- Maximum matching and a polyhedron with 0,1-vertices
- Revised Matrix Algorithms for Shortest Paths
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
