c******n
发帖数: 4965 | 1 【 以下文字转载自 Mathematics 讨论区 】
发信人: creation (努力自由泳50m/45sec !), 信区: Mathematics
标 题: graph question: what is "genus" ?
发信站: BBS 未名空间站 (Wed May 29 18:58:51 2013, 美东)
tried to read wikipedia but still got very confused
in this paragraph:
"
The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus
Shayan Oveis Gharan∗ Amin Saberi∗
.....
We present the first constant-factor approximation algorithm for the
Asymmetric Traveling Salesman
Problem (ATSP) for metrics defined by a weighted directed graph with a
bounded orientable genus.
This is a natural special case: consider a metric obtained by shortest path
distances in a city with one
way streets and a constant number of bridges and underpasses.
"
could someone please tell me what is the genus in a completely-connected
graph with N nodes (i.e. with N*(N-1) edges)
thanks | r********n
发帖数: 7441 | 2 roughly the number of isolated subspaces formed by the convex combination of
feasible points
【在 c******n 的大作中提到】
: 【 以下文字转载自 Mathematics 讨论区 】
: 发信人: creation (努力自由泳50m/45sec !), 信区: Mathematics
: 标 题: graph question: what is "genus" ?
: 发信站: BBS 未名空间站 (Wed May 29 18:58:51 2013, 美东)
: tried to read wikipedia but still got very confused
: in this paragraph:
: "
: The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus
: Shayan Oveis Gharan∗ Amin Saberi∗
: .....
|
|
