Talk:Chinese postman problem

[Untitled]

Is the information here relevance to the "route inspection problem"? It seems a little bit off topic to me. Dysprosia 11:23, 2 Oct 2003 (UTC)

It seems that the drfinition of the rural postman problem should be change to 'find a minimum weight closed route that traverses a given set of edges' (shuroo)

The article says:

It should, however, be noted, that this is only a condition that ensure that a Hamiltonian cycle exist, we cannot conclude the other way

but above it, it says "if and only if". Which is it?

It is not about Hamiltonian (going through nodes) but about Eulerian (going through edges) cycles. A non-oriented connected graph G=(V,E) has an Eulerian cycle if and only if all nodes have even degree.

Eulerian paths and circuits

The article says:

1 → 2

2 → 3

3 → 1

Is this a correct way of demonstrating the validity of those equivalences? --213.100.56.253 00:46, 24 May 2007 (UTC)

Eulerian vs semi-eulerian/traversable

The "Solution" section deals only with eulerian and non-eulerian graphs, stating that if the graph is eulerian, an eulerian path can be found, otherwise another method can give the shortest path possible. However, wouldn't it be more appropriate to make the distinction between semi-eulerian graphs and non-semi-eulerian graphs? Because all semi-eulerian graphs, whether they are also eulerian or not, have eulerian paths. (Tanynep (talk) 12:24, 10 May 2009 (UTC))

I think not. The problem when odd-degree vertices exist is solved by reduction to the case when all vertex degrees are even. Thus, the natural division is between the case with odd degrees and the case without any. Zaslav (talk) 04:29, 27 April 2010 (UTC)

Path, trail, walk, circuit

The standard usage in graph theory is that a path has no repeated vertices or edges. A trail has no repeated vertices, but it may repeat edges. A walk has no repeated vertices or edges.

A closed walk or trail has the same initial and final vertices. An open walk or trail has different initial and final vertices. A closed path is a closed trail that doesn't repeat a vertex except for the initial and final vertices.

A circuit may be several things. It may be a closed path (or the graph of a closed path), which is also usually called a cycle; or it may be a closed trail.

These are graph-theory customs. The customary terminology in electrical engineering, computer science, or social network analysis may differ in various ways.

See almost any graph theory book written by mathematicians (as opposed to engineers, et al.): Bondy and Murty; Diestel; Bollobas; others that I don't remember at the moment. Zaslav (talk) 05:26, 28 April 2010 (UTC)

See Glossary of graph theory#Walks:

• "A walk is an alternating sequence of vertices and edges."
• "A trail is a walk in which all the edges are distinct."
• "Traditionally, a path referred to what is now usually known as an open walk. Nowadays, when stated without any qualification, a path is usually understood to be simple, meaning that no vertices (and thus no edges) are repeated."

Justin W Smith ^talk/_stalk 05:31, 28 April 2010 (UTC) (Updated: 14:23, 28 April 2010 (UTC))

@Zaslav: Your definition of "trail" appears to differ from that used on Wikipedia. Justin W Smith ^talk/_stalk 05:34, 28 April 2010 (UTC)

In this article, "path" is used to mean "open walk". It might be appropriate to change "path" to "walk", but not to "trail". Justin W Smith ^talk/_stalk 05:39, 28 April 2010 (UTC)

Seems incorrect. Or are you saying that a Eulerian "path" isn't a path? I can assure you that Eulerian path is the term used. Perhaps the glossary is in error. — Arthur Rubin (talk) 08:15, 28 April 2010 (UTC)

The glossary is consistent with my understanding of the usage of the terms. A few points:

• I have no problem using the term "path" as a generic term for an "open walk". This is "traditionally" how it was used.
• Unless every vertex has degree 2 (except the end points), the "Eulerian path" is not a "simple path". However, since any "Eulerian path" does visit every edge exactly once, it would more precisely be a "trail".
• Unless every vertex is of even degree (necessary and sufficient condition for an "Eulerian cycle" to exist), the "shortest closed path ... that visits every edge of a (connected) undirected graph" is not even a "trail". That is, the solution visits some edges more than once; in this case, the solution would most accurately described as an "closed walk".

Justin W Smith ^talk/_stalk 13:35, 28 April 2010 (UTC)

"Eulerian trail" is used for the open trail, and "Eulerian path" is also used. "Eulerian tour" and "Eulerian circuit" are used for the closed trail. You seem to be saying "path" is not correct but you insist on using it. Why? See Talk:Eulerian path for more.

An Eulerian trail/path does not repeat edges. The correct statement is that a graph does not have an Eulerian trail/path if it is necessary to repeat edges. I do not understand why you say different. Zaslav (talk) 16:51, 28 April 2010 (UTC)

Are we talking specifically about this article? (I feel like we're instead talking about the Eulerian path article.) Anyways, a solution to the problem (in this article) that happens to be an "Eulerian trail" is a special case, for which finding the solution is trivial. In general, the solution to this problem is not a "trail" and is not "Eulerian"; the solution is very likely to have repeated edges. I don't think I've been inconsistent in what I've said. Justin W Smith ^talk/_stalk 18:13, 28 April 2010 (UTC)

@Zaslav: Re: "I do not understand why you say different." I didn't say something contrary to your claim: "a graph does not have an Eulerian trail/path if it is necessary to repeat edges". I agree. Maybe I wasn't clear earlier. Justin W Smith ^talk/_stalk 18:26, 28 April 2010 (UTC)

@Justin W Smith: It looks like I was confused. We agree that a solution to the postman problem is a closed walk that may repeat edges. The word "Eulerian" doesn't belong there. I was working on Eulerian path at the same time; maybe that was the reason. Anyway, I apologize for wasting your time on that. As for "Eulerian path/trail" (the 0 or 2 odd vertices case), I think "trail" is a better choice for WP but it's not worth my time pursuing. Zaslav (talk) 16:33, 29 April 2010 (UTC)

Who was Mei-Ko Kwan?

Does anyone know anything about Mei-Ko Kwan the person himself? His name is conspicuous by its complete absence anywhere on the Net other than a brief sentence about how he deduced the Chinese Postman algorithm. There aren't even any photos of him, or any information about where he was born/died or where he lived and did his work.

This is especially odd considering he published his algorithm in 1962, which can't have been easy considering that China was probably one of the worst places to be seen to be an intellectual at the time. — Preceding unsigned comment added by Holy triple m (talk • contribs) 15:30, 21 February 2011 (UTC)

T-paths

The whole T-paths section is a complete mess. Where are you getting 1/2 |T| "paths" from? What is this. —Preceding unsigned comment added by 24.15.220.182 (talk) 01:55, 26 April 2011 (UTC)

See e.g. Korte, Vygen: Combinatorial Optimization. (Lemma 12.8). There are |T|/2 paths because there are |T| many vertices with odd degree that have to be covered (each path does 2 of them). Additionally, there may be some circuits, too. A path is defined (at least in Korte, Vygen) as sequence of vertices and edges, all being pairwise disjoint. I don't see a problem with that. --Star Flyer (talk) 21:08, 18 January 2013 (UTC)

Mistake? Text says: T=empty, then smallest T-join solves postman problem

The text says: "When T is the empty set, a smallest T-join leads to a solution of the postman problem." But Schrijver's book, Corollary 29.1d, gives us a solution of that problem by T=vertices of odd degree. Did I misunderstand something or is there an error in the text? --Star Flyer (talk) 20:51, 18 January 2013 (UTC)

Merger proposal

I propose that Chinese postman problem be merged into Route inspection problem.

Rural Salesman

The article implies that the Rural Salesman (not every edge required) is considered NP-complete, however the source on Rural Salesman is behind a paywall and the citation for the assertion doesn't mention the Rural Salesman. It seems un-intuitive that the original would be P while this variant is NP. If this is the case, an explanation added (or at least a source) would be helpful 50.241.129.75 (talk) 20:40, 8 November 2017 (UTC)

Off-topic material

In Special:Diff/1085693210 I removed a huge pile of material describing metaheuristics for variant problems, added by User:ScientistBuilder, almost completely off-topic to the main subject of this article, and five times as long as the on-topic content of the article. This is not the place for describing those problems in such detail. Adding it here totally unbalances the article. —David Eppstein (talk) 23:12, 1 May 2022 (UTC)

Is my work totally deleted or is there a place for it? ScientistBuilder (talk) 23:57, 1 May 2022 (UTC)

I worked for a long time on compiling this information why are Wikipedia policies against it? If Wikipedia is not the place for this where can I go to post it? For example Wikipedia:OUT and Wikipedia:What Wikipedia is not? What in the Wikipedia:Five pillars is against my work? @David Eppstein ScientistBuilder (talk) 23:59, 1 May 2022 (UTC)

I think the article could be reorganized with a focus on how each problem works.

There is a lot of material that is not covered now that the work is deleted. For example, arc routing problems and Eulerian graphs. ScientistBuilder (talk) 00:03, 2 May 2022 (UTC)

See WP:NPOV and the word "proportionally" in the first sentence. This article is not the place for maunderings on generalized variations of arc routing problems. It is specifically for the route inspection problem. —David Eppstein (talk) 00:17, 2 May 2022 (UTC)

@David Eppstein Wikipedia:FIXTHEPROBLEM

Instead of removing article content that is poorly presented, consider cleaning up the writing, formatting or sourcing on the spot, or tagging it as necessary. If you think an article needs to be rewritten or changed substantially, go ahead and do so, but it is best to leave a comment about why you made the changes on the article's talk page. ScientistBuilder (talk) 00:20, 2 May 2022 (UTC)

@David Eppstein Where should I place this work? If my work is getting kicked off the Route Inspection Page, could I create a new page? ScientistBuilder (talk) 00:21, 2 May 2022 (UTC)

@David Eppstein "See WP:NPOV and the word "proportionally" in the first sentence. This article is not the place for maunderings on generalized variations of arc routing problems. It is specifically for the route inspection problem"

"All encyclopedic content on Wikipedia must be written from a neutral point of view (NPOV), which means representing fairly, proportionately, and, as far as possible, without editorial bias, all the significant views that have been published by reliable sources on a topic."

I don't understand what point of view is being overrepresented and underrepresented to have no bias. ScientistBuilder (talk) 00:23, 2 May 2022 (UTC)

You are overrepresenting material that is not about the route inspection problem and underrepresenting material on the core topic of this article. A hint: the route inspection problem is, as it says in the first sentence, on "a shortest closed path or circuit that visits every edge". It has a polynomial time algorithm. If you are writing about other problems of finding paths or circuits with other constraints that do not have polynomial time algorithms, you are off-topic. In short, you are hijacking an article on a notable topic to write about something else. —David Eppstein (talk) 00:25, 2 May 2022 (UTC)

I will make edits to Arc routing which are all NP-hardness. Is this a good compromise? I don't want to lose my work.

I am working on following this: https://en.wikipedia.org/wiki/Help:Wikipedia:_The_Missing_Manual/Collaborating_with_other_editors/Resolving_content_disputes#Look_for_compromises ScientistBuilder (talk) 00:37, 2 May 2022 (UTC)

@David Eppstein "If you are writing about other problems of finding paths or circuits with other constraints that do not have polynomial time algorithms, you are off-topic." I am going to write NP hard graph theory algorithms in Arc routing.

"In short, you are hijacking an article on a notable topic to write about something else"

"Assuming good faith (AGF) is a fundamental principle on Wikipedia. It is the assumption that editors' edits and comments are made in good faith – that is, the assumption that people are not deliberately trying to hurt Wikipedia, even when their actions are harmful. Most people try to help the project, not hurt it."

WP:GOODFAITH ScientistBuilder (talk) 00:47, 2 May 2022 (UTC)

I never said anything about why I thought you might be hijacking the article, so questions about my belief in your good faith are also off-topic. You know, if you find it upsetting when people state directly what they find inappropriate about your edits, you could try being more responsive to the discussion at an earlier stage, before your demands for more and more of an explanation lead people to state things directly. —David Eppstein (talk) 01:02, 2 May 2022 (UTC)

Requested move 8 October 2022

The following is a closed discussion of a requested move. Please do not modify it. Subsequent comments should be made in a new section on the talk page. Editors desiring to contest the closing decision should consider a move review after discussing it on the closer's talk page. No further edits should be made to this discussion.

The result of the move request was: moved. (non-admin closure) Rotideypoc41352 (talk · contribs) 03:30, 16 October 2022 (UTC)

---

Route inspection problem → Chinese postman problem – I would like to suggest renaming the article to Chinese Postman Problem. WalkingRadiance (talk) 19:26, 8 October 2022 (UTC)

The renaming process would change the redirect from Chinese Postman Problem to the main article and Route Inspection Problem would redirect to Chinese Postman Problem. WalkingRadiance (talk) 19:27, 8 October 2022 (UTC)

"Chinese Postman Problem" is definitely the wrong title; we don't capitalize like that on Wikipedia. Chinese postman problem exists and is a redirect to this article. It does seem to be true that "Chinese postman problem" is the more WP:COMMONNAME for this problem, even among very recent publications. Given that our article documents that the name was given to honor a specific Chinese mathematician, rather than as an instance of racist stereotyping, I don't think moving the article to Chinese postman problem over the redirect would be problematic. —David Eppstein (talk) 20:15, 8 October 2022 (UTC)

• support in my experience its the common name but ngrams here: [1])—blindlynx 16:05, 9 October 2022 (UTC)

  I support the move. WalkingRadiance (talk) 21:04, 15 October 2022 (UTC)

  Since there is no one opposed, I would like to request someone who knows how to move the article to do so such as administrator. WalkingRadiance (talk) 01:31, 16 October 2022 (UTC)

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.