Naturally submodular digraphs and forbidden digraph configurations

DOI10.1016/S0166-218X(99)00167-5zbMath0939.05070OpenAlexW2088030665MaRDI QIDQ1962020

Frieda Granot, Weiping R. Zhu, Daniel Granot

Publication date: 5 July 2000

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00167-5

zbMATH Keywords

characterizationsgraph decompositionsforbidden digraph configurationsSteiner toursubmodular digraphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Directed graphs (digraphs), tournaments (05C20)

Related Items

Characterizing convexity of games using marginal vectors ⋮ Operations research games: A survey. (With comments and rejoinder) ⋮ Submodularity and the traveling salesman problem ⋮ On the equivalence between some local and global Chinese postman and traveling salesman graphs ⋮ On the submodularity of multi-depot traveling salesman games ⋮ Traveling salesman games with the Monge property ⋮ On the properties of weighted minimum colouring games

Cites Work

• Unnamed Item
• Submodularity and the traveling salesman problem
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• The kernel/nucleolus of a standard tree game
• On some balanced, totally balanced and submodular delivery games
• Cores of convex games
• The kernel and bargaining set for convex games
• Simple Power-of-Two Policies are Close to Optimal in a General Class of Production/Distribution Networks with General Joint Setup Costs
• Computational Complexity of the Game Theory Approach to Cost Allocation for a Tree
• Characterizations of Natural Submodular Graphs: A Polynomially Solvable Class of the TSP
• Heuristics for a One-Warehouse Multiretailer Distribution Problem with Performance Bounds
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: Naturally submodular digraphs and forbidden digraph configurations