On the Equivalence between some Local and Global Chinese Postman and Traveling Salesman Graphs

D. Granot, H.J.M. Hamers

Research output: Working paperDiscussion paperOther research output

234 Downloads (Pure)

Abstract

A connected graph G=(V,E), a vertex in V and a non-negative weight function defined on Ecan be used to induce Chinese postman and traveling salesman (cooperative) games. A graph G=(V,E) is said to be locally (respectively, globally) Chinese postman balanced (respectively, totally balanced, submodular) if for at least one vertex (respectively, for all vertices) in V and any non-negative weight function defined on E, the corresponding Chinese postman game is balanced (respectively, totally balanced, submodular). Local and global traveling salesman balanced (respectively, totally balanced, submodular) graphs are similarly defined. In this paper we study the equivalence between local and global Chinese postman balanced (respectively, totally balanced, submodular) graphs, and between local and global traveling salesman submodular graphs.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages14
Volume2000-48
Publication statusPublished - 2000

Publication series

NameCentER Discussion Paper
Volume2000-48

Fingerprint

Travelling salesman
Equivalence
Graph in graph theory
Weight Function
Non-negative
Cooperative Game
Vertex of a graph
Connected graph
Game

Keywords

  • cooperative game
  • Chinese postman
  • traveling salsesman
  • core
  • submodularity

Cite this

Granot, D., & Hamers, H. J. M. (2000). On the Equivalence between some Local and Global Chinese Postman and Traveling Salesman Graphs. (CentER Discussion Paper; Vol. 2000-48). Tilburg: Operations research.
Granot, D. ; Hamers, H.J.M. / On the Equivalence between some Local and Global Chinese Postman and Traveling Salesman Graphs. Tilburg : Operations research, 2000. (CentER Discussion Paper).
@techreport{105e99db770e4f9c9a8451a8bab05dd6,
title = "On the Equivalence between some Local and Global Chinese Postman and Traveling Salesman Graphs",
abstract = "A connected graph G=(V,E), a vertex in V and a non-negative weight function defined on Ecan be used to induce Chinese postman and traveling salesman (cooperative) games. A graph G=(V,E) is said to be locally (respectively, globally) Chinese postman balanced (respectively, totally balanced, submodular) if for at least one vertex (respectively, for all vertices) in V and any non-negative weight function defined on E, the corresponding Chinese postman game is balanced (respectively, totally balanced, submodular). Local and global traveling salesman balanced (respectively, totally balanced, submodular) graphs are similarly defined. In this paper we study the equivalence between local and global Chinese postman balanced (respectively, totally balanced, submodular) graphs, and between local and global traveling salesman submodular graphs.",
keywords = "cooperative game, Chinese postman, traveling salsesman, core, submodularity",
author = "D. Granot and H.J.M. Hamers",
note = "Pagination: 14",
year = "2000",
language = "English",
volume = "2000-48",
series = "CentER Discussion Paper",
publisher = "Operations research",
type = "WorkingPaper",
institution = "Operations research",

}

Granot, D & Hamers, HJM 2000 'On the Equivalence between some Local and Global Chinese Postman and Traveling Salesman Graphs' CentER Discussion Paper, vol. 2000-48, Operations research, Tilburg.

On the Equivalence between some Local and Global Chinese Postman and Traveling Salesman Graphs. / Granot, D.; Hamers, H.J.M.

Tilburg : Operations research, 2000. (CentER Discussion Paper; Vol. 2000-48).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - On the Equivalence between some Local and Global Chinese Postman and Traveling Salesman Graphs

AU - Granot, D.

AU - Hamers, H.J.M.

N1 - Pagination: 14

PY - 2000

Y1 - 2000

N2 - A connected graph G=(V,E), a vertex in V and a non-negative weight function defined on Ecan be used to induce Chinese postman and traveling salesman (cooperative) games. A graph G=(V,E) is said to be locally (respectively, globally) Chinese postman balanced (respectively, totally balanced, submodular) if for at least one vertex (respectively, for all vertices) in V and any non-negative weight function defined on E, the corresponding Chinese postman game is balanced (respectively, totally balanced, submodular). Local and global traveling salesman balanced (respectively, totally balanced, submodular) graphs are similarly defined. In this paper we study the equivalence between local and global Chinese postman balanced (respectively, totally balanced, submodular) graphs, and between local and global traveling salesman submodular graphs.

AB - A connected graph G=(V,E), a vertex in V and a non-negative weight function defined on Ecan be used to induce Chinese postman and traveling salesman (cooperative) games. A graph G=(V,E) is said to be locally (respectively, globally) Chinese postman balanced (respectively, totally balanced, submodular) if for at least one vertex (respectively, for all vertices) in V and any non-negative weight function defined on E, the corresponding Chinese postman game is balanced (respectively, totally balanced, submodular). Local and global traveling salesman balanced (respectively, totally balanced, submodular) graphs are similarly defined. In this paper we study the equivalence between local and global Chinese postman balanced (respectively, totally balanced, submodular) graphs, and between local and global traveling salesman submodular graphs.

KW - cooperative game

KW - Chinese postman

KW - traveling salsesman

KW - core

KW - submodularity

M3 - Discussion paper

VL - 2000-48

T3 - CentER Discussion Paper

BT - On the Equivalence between some Local and Global Chinese Postman and Traveling Salesman Graphs

PB - Operations research

CY - Tilburg

ER -

Granot D, Hamers HJM. On the Equivalence between some Local and Global Chinese Postman and Traveling Salesman Graphs. Tilburg: Operations research. 2000. (CentER Discussion Paper).