Template:Did you know nominations/Halin graph
Jump to navigation
Jump to search
Overall: Long enough, new enough, well sourced, neutral, no copyvio. Both the hook and the article itself are really interesting. Ready to go! Zin Win Hlaing (talk) 04:09, 24 July 2021 (UTC)
- The following is an archived discussion of the DYK nomination of the article below. Please do not modify this page. Subsequent comments should be made on the appropriate discussion page (such as this nomination's talk page, the article's talk page or Wikipedia talk:Did you know), unless there is consensus to re-open the discussion at this page. No further edits should be made to this page.
The result was: promoted by Desertarun (talk) 15:15, 1 August 2021 (UTC)
DYK toolbox |
---|
Halin graph
- ... that when a tree is a star, connecting its leaves in a cycle makes a wheel? Source: Cornuéjols et al (1983), Halin graphs and the travelling salesman problem: "If T is a star, i.e., a single node v joined to n other nodes, then H is called a wheel and is the simplest type of Halin graph."
- ALT1:... that many hard combinatorial optimization problems are easier on Halin graphs because of their low treewidth? Source: Bodlaender (1988), Dynamic programming on graphs with bounded treewidth: "we show for a large number of graph decision problems ... the existence of O(n^C) or polynomial algorithms for these problems, restricted to the graphs with bounded treewidth"
- Reviewed: Sacred Heart of Jesus (Batoni)
Improved to Good Article status by David Eppstein (talk). Self-nominated at 00:39, 21 July 2021 (UTC).
General: Article is new enough and long enough |
---|
Policy: Article is sourced, neutral, and free of copyright problems |
---|
|
Hook: Hook has been verified by provided inline citation |
---|
|
QPQ: Done. |