Naturally submodular digraphs and forbidden digraph configurations

DOI10.1016/S0166-218X(99)00167-5zbMATH Open0939.05070OpenAlexW2088030665MaRDI QIDQ1962020FDOQ1962020

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

Recommendations

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

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)

Cites Work

• 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
• Computational Complexity of the Game Theory Approach to Cost Allocation for a Tree
• Depth-First Search and Linear Graph Algorithms
• Title not available (Why is that?)
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• Simple Power-of-Two Policies are Close to Optimal in a General Class of Production/Distribution Networks with General Joint Setup Costs
• Heuristics for a One-Warehouse Multiretailer Distribution Problem with Performance Bounds
• Submodularity and the traveling salesman problem
• Characterizations of Natural Submodular Graphs: A Polynomially Solvable Class of the TSP

Cited In (8)

• On the submodularity of multi-depot traveling salesman games
• On the equivalence between some local and global Chinese postman and traveling salesman graphs
• Submodularity and the traveling salesman problem
• 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)