Jump to content

Talk:Cop-win graph/GA1

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

GA Review

[edit]

Article (edit | visual edit | history) · Article talk (edit | history) · Watch

Reviewer: Eviolite (talk · contribs) 05:11, 23 April 2022 (UTC)[reply]

I will review this nomination within the next ~2 days; please ping me if I do not get back by then. eviolite (talk) 05:11, 23 April 2022 (UTC)[reply]

GA review (see here for what the criteria are, and here for what they are not)
  1. It is reasonably well written.
    a (prose, spelling, and grammar): b (MoS for lead, layout, word choice, fiction, and lists):
    Prose comments below
  2. It is factually accurate and verifiable.
    a (reference section): b (citations to reliable sources): c (OR): d (copyvio and plagiarism):
    Passes spotchecks
  3. It is broad in its coverage.
    a (major aspects): b (focused):
    Doesn't miss anything obvious
  4. It follows the neutral point of view policy.
    Fair representation without bias:
    Tone is good
  5. It is stable.
    No edit wars, etc.:
    No edits by other people in years (only bots)
  6. It is illustrated by images and other media, where possible and appropriate.
    a (images are tagged and non-free content have non-free use rationales): b (appropriate use with suitable captions):
    All free with clear pertinence to the article and captions
  7. Overall:
    Pass/Fail:

Prose comments

[edit]

Lead

[edit]
  • Citation should be removed per MOS:LEADCITE and that the information is present in the Definitions section

Definitions

[edit]

Closure properties

[edit]

Recognition algorithms

[edit]
  • Link degree (graph theory) as the term may not be familiar to readers
  • The whole decrementing thing seems equivalent to just re-calculating the number of triangles for each edge, so maybe remove "repeatedly" and that clause, instead saying "and repeat these steps for the now-smaller graph". I don't know if that constitutes OR, though, since it seems the original paper also used the "updating" wording, so it's your call.
    • Um, no, this would be a problem. Finding and counting all triangles is slow, so you don't want to do that over and over again every time you remove one vertex. Counting them once and updating the counts avoids this slow recalculation. —David Eppstein (talk) 07:44, 30 April 2022 (UTC)[reply]
  • It's not immediately clear where the alternative time complexity comes from, perhaps because it's not made explicit where the original n^3/log n comes from either (without digging through the source), so I'd treat this as OR and fall back on the time from the paper, perhaps with an in-text attribution though.
    • The analysis parts of the bullet points in this section were more or less my notes to myself at trying to figure out where the n^3/log n comes from and concluding that the analysis was sloppy and it's really mn/log n. But I suppose without a source we can't actually say that; it's not simple enough for WP:CALC. So I jjust removed it and quoted the n^3/log n. It makes less difference than you might think, because this algorithm is only an improvement on the O(dm) one when mn is within a logarithmic factor of n^3 (another thing we probably shouldn't say without sourcing). —David Eppstein (talk) 08:05, 1 May 2022 (UTC)[reply]
  • In the "In infinite graphs" section, it's not really clear to me what differentiates "algorithmically" from having unbounded computing power; is it that any finite algorithm can't beat the robber? A clarification might be warranted though I might just be missing something.
    • This is a basic point about computation rather than anything specific to this article's topic. Computers, even theoretical ones, are (like people) not omniscient. There are plenty of things we might want them to compute but we can prove are uncomputable. There is an answer but no algorithm can find one. Testing whether a given computer program contains an infinite loop, for instance. You can program up heuristics that sometimes find infinite loops, but there will always be an input that they fail on (by giving the wrong answer or getting into an infinite loop themselves). That background was the point of linking computability at the start of this section. Anyway, I changed "with unbounded computing power" to "omniscient" in hope that this will be less confusing. —David Eppstein (talk) 07:30, 1 May 2022 (UTC)[reply]
[edit]

@David Eppstein: Placing on hold for now. eviolite (talk) 03:04, 25 April 2022 (UTC)[reply]

Thanks! My time is tight for the next few days but I'll see what I can do. —David Eppstein (talk) 05:31, 25 April 2022 (UTC)[reply]
@Eviolite: Ok, I think I've responded to everything — please take another look. —David Eppstein (talk) 16:42, 1 May 2022 (UTC)[reply]
Thank you for the response. I see you have also done some other copy-edits to the Recognition algorithms section, which I appreciate. Happy to promote now; great work. eviolite (talk) 05:19, 2 May 2022 (UTC)[reply]