On the complexity of edge traversing

DOI10.1145/321958.321974MaRDI QIDQ4121714zbMATH OpenOpenAlexWikidataFDO

Authors Christos Papadimitriou

Publication date 1976

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/321958.321974

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Integer programming (90C10) Programming involving graphs or networks (90C35)

Cited in

(44)

• Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width
• On negative cycles in mixed graphs
• A cutting plane algorithm for the windy postman problem
• The maximum benefit Chinese postman problem and the maximum benefit traveling salesman problem
• On the mixed Chinese postman problem
• Algorithms for the windy postman problem
• Multiple center capacitated arc routing problems: A tabu search algorithm using capacitated trees
• Minimal length test vectors for multiple-fault detection
• A GRASP heuristic for the mixed Chinese postman problem
• Colored homomorphisms of colored mixed graphs
• Solvable cases of the \(k\)-person Chinese postman problem
• Algorithms for the Chinese postman problem on mixed networks
• Routing problems: A bibliography
• The Chinese deliveryman problem
• Postman problems on series-parallel mixed graphs
• Domino sequencing: scheduling with state-based sequence-dependent setup times
• New results on the windy postman problem
• Solution of real-world postman problems
• A comparison of two different formulations for arc routing problems on mixed graphs
• Covering partially directed graphs with directed paths
• The mixed Chinese postman problem parameterized by pathwidth and treedepth
• Approximation algorithms for a mixed postman problem with restrictions on the arcs
• Approximation algorithms for solving the constrained arc routing problem in mixed graphs
• Rural postman parameterized by the number of components of required edges
• Parameterized complexity of the k-arc Chinese postman problem
• Structural parameterizations of the mixed Chinese postman problem
• A decade of capacitated arc routing
• Genetic algorithm for Chinese postman problems
• Reconstructing strings from substrings (Extended abstract)
• Chinese postman problem on edge-colored multigraphs
• Modeling and solving the endpoint cutting problem
• Arc routing problems: A review of the past, present, and future
• Traversability, reconfiguration, and reachability in the gadget framework
• Approximation algorithms for the min-max mixed rural postmen cover problem and its variants
• Approximation algorithms for the min-max mixed rural postmen cover problem and its variants
• Approximation algorithms for solving the vertex-traversing-constrained mixed Chinese postman problem
• Computational complexity of the police officer patrol problem on weighted digraphs
• A survey of some operations research and data sciences applications developed in the last 20 years at argentinian and chilean universities
• Exact and approximation algorithms for routing a convoy through a graph
• City streets parking enforcement inspection decisions: the Chinese postman's perspective
• Minimum cost nowhere-zero flows and cut-balanced orientations
• The mixed postman problem
• On the windy postman problem
• The arc partitioning problem

This page was built for publication: On the complexity of edge traversing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4121714)