Naturally submodular digraphs and forbidden digraph configurations

DOI10.1016/S0166-218X(99)00167-5MaRDI QIDQ1962020zbMATH OpenOpenAlexFDO

Authors Frieda Granot, Daniel Granot, Weiping R. Zhu

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

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

Recommendations

• Characterizations for special directed co-graphs
• On the submodular matrix representation of a digraph.
• Some new good characterizations for directed graphs
• scientific article; zbMATH DE number 4144022
• Forbidden ordered subgraph vs. forbidden subgraph characterizations of graph classes

Cites work

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

Cited in

(8)

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

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

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