Characterizations of Natural Submodular Graphs: A Polynomially Solvable Class of the TSP

DOI10.2307/2160785MaRDI QIDQ4327639zbMATH OpenOpenAlexFDO

Authors Yale T. Herer, Michal Penn

Publication date 10 April 1995

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/2160785

zbMATH Keywords

closed walknaturally submodular graphsSteiner tourtravelling salesman problem

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Polynomial time algorithms for two classes of subgraph problem
• Polynomial-time algorithms for submodular Laplacian systems
• A subexponential parameterized algorithm for subset TSP on planar graphs
• Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
• Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
• A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
• Naturally submodular digraphs and forbidden digraph configurations
• A strongly polynomial time algorithm for a constrained submodular optimization problem
• Classes of subcubic planar graphs for which the independent set problem is polynomially solvable

Cited in

(8)

• Submodularity and the traveling salesman problem
• Operations research games: A survey. (With comments and rejoinder)
• On the submodularity of multi-depot traveling salesman games
• Naturally submodular digraphs and forbidden digraph configurations
• On the properties of weighted minimum colouring games
• Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs
• On the convexity of independent set games
• Clique partitioning of interval graphs with submodular costs on the cliques

This page was built for publication: Characterizations of Natural Submodular Graphs: A Polynomially Solvable Class of the TSP

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