Naturally submodular digraphs and forbidden digraph configurations
type: Item
instance of: scholarly article
title: Naturally submodular digraphs and forbidden digraph configurations
zbMATH Open document ID: 0939.05070
DOI: 10.1016/S0166-218X(99)00167-5
author: Frieda Granot
author: Daniel Granot
author: Weiping R. Zhu
published in: Discrete Applied Mathematics
publication date: 2000-07-05T00:00:00Z
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.
reviewed by: Wai-Kai Chen
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 1394991
zbMATH Keywords: Steiner tour
zbMATH Keywords: characterizations
zbMATH Keywords: submodular digraphs
zbMATH Keywords: forbidden digraph configurations
zbMATH Keywords: graph decompositions
MaRDI profile type: Publication
cites work: Q3097395
cites work: Simple Power-of-Two Policies are Close to Optimal in a General Class of Production/Distribution Networks with General Joint Setup Costs
cites work: On some balanced, totally balanced and submodular delivery games
cites work: The kernel/nucleolus of a standard tree game
cites work: Submodularity and the traveling salesman problem
cites work: Characterizations of Natural Submodular Graphs: A Polynomially Solvable Class of the TSP
cites work: Heuristics for a One-Warehouse Multiretailer Distribution Problem with Performance Bounds
cites work: The kernel and bargaining set for convex games
cites work: Computational Complexity of the Game Theory Approach to Cost Allocation for a Tree
cites work: Linear algorithms to recognize outerplanar and maximal outerplanar graphs
cites work: Cores of convex games
cites work: Depth-First Search and Linear Graph Algorithms
full work available at URL: s0166-218x(99)00167-5
OpenAlex ID: W2088030665
description: scientific article; zbMATH DE number 1394991