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

characterizationsforbidden digraph configurationsgraph decompositionsSteiner toursubmodular digraphs

Mathematics Subject Classification ID

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

Review text

The authors present several characterizations of the classes of naturally submodular digraphs and naturally submodular bidirected graphs. For each class, one characterization is given in terms of forbidden digraph configurations and the other in terms of graph decompositions. For the class of bidirected graphs, an additional characterization in terms of the fixed-order property is derived. Specifically, it is shown that naturally submodular digraphs are 1-sums of a certain type of outerplanar digraphs, and naturally submodular bidigraphs can be characterized in terms of the fixed-order property, and that this latter property is not a characteristic of naturally submodular digraphs.

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)

• Submodularity and the traveling salesman problem
• Operations research games: A survey. (With comments and rejoinder)
• 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
• Characterizing convexity of games using marginal vectors
• On the properties of weighted minimum colouring games
• Characterizations of Natural Submodular Graphs: A Polynomially Solvable Class of the TSP

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)