Pith. sign in

REVIEW 3 major objections 3 minor 42 references

A Practical Linear Time Algorithm for Optimal Tree Decomposition of Halin Graphs

T0 review · 3 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper claims that H-TD computes a width-three tree decomposition of every Halin graph in linear time, and that this width is optimal.

desk verdict A plausible and practically motivated linear-time tree decomposition for Halin graphs, but the proof has two load-bearing gaps that need patching before the central claim is established. read the letter →

arxiv 2506.02346 v1 pith:IOJXQFHD submitted 2025-06-03 cs.DS

J.A. Alejandro-Soto , Joel Antonio Trejo-Sanchez , Carlos Segura This is my paper
classification cs.DS MSC 68R1005C8568Q25
keywords treedecompositionHalingraphstreewidthlinear-timealgorithmAlmostgraphalgorithms
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that H-TD, a structural algorithm, computes a tree decomposition of width three for every Halin graph in time linear in the number of vertices. Because Halin graphs have treewidth three, the resulting decomposition is optimal. The significance is practical: general linear-time algorithms for treewidth at most k exist but have huge hidden constants, and reduction-rule methods become unmanageably complex for k = 4 and beyond. H-TD instead reads off the Halin skeleton and leaf cycle, orders adjacency lists so a depth-first search follows the leaf cycle, and recursively glues together decompositions of two overlapping Almost Halin subgraphs. The paper reports that on Halin instances with up to roughly a million vertices the algorithm runs in seconds, while general-purpose exact solvers time out or exhaust memory and heuristics do not reach width three.

What carries the argument

The load-bearing object is the pair of recursive subgraphs called Almost Halin type 1 (AH1) and type 2 (AH2). An AHt(v,i,j) is induced by a skeleton vertex v, the subtrees of a consecutive block of v's children, and (for type 1) one extra leaf-neighbor; its three representatives are v, the first leaf in the first child subtree, and the last leaf in the last child subtree. The recursive procedure AH-TD uses the identity that AHt(v,i,j) can be split into AH1(v,i,i) and AHt(v,i+1,j): the two pieces share only two representative vertices, so a local bag tree whose central bag contains the shared representatives lets the two child decompositions be pasted into a valid tree decomposition. The linear-time adjacency order is what guarantees that the intervals of leaves covered by consecutive child subtrees are contiguous along the leaf cycle, which is exactly why the split-and-paste construction works.

What would settle it

Run H-TD on a Halin graph and validate the returned decomposition with a standard checker for the three tree-decomposition conditions; a single violation of the connectivity condition, or a single repeated recursive call in an instrumented run, would refute the main claim.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that the Halin structure itself is enough to build an optimal decomposition directly. Every Halin graph consists of a plane tree (the skeleton) plus a cycle through its leaves. H-TD roots the skeleton, gives each vertex an adjacency order compatible with a traversal of the leaf cycle, and then calls a recursive procedure AH-TD on the whole graph. The recursion decomposes an Almost Halin type 1 or type 2 subgraph into two strictly smaller Almost Halin subgraphs that overlap only in their root and one leaf, so their decompositions can be connected through a small local bag tree whose bags are the representatives of the two subgraphs. Since every bag has at most four vertices, the output has width three; since Halin graphs have treewidth three, this is optimal. The experimental section additionally claims that the implementation outperforms existing exact and heuristic solvers on Halin instances across four size ranges, and that its outputs pass a standard validator.

Load-bearing premise

Everything depends on the recursive construction never looping and on every vertex appearing in a connected block of bags; the paper does not fully prove either point, since the proof of Corollary 1 invokes itself and Proposition 3 promises an explicit check that it does not show.

Editorial extensions

If this is right

  • Any Halin graph can be decomposed in linear time into bags of at most four vertices, and no smaller width is possible because Halin graphs have treewidth three.
  • Algorithms for NP-hard problems that run in polynomial time on bounded-treewidth graphs become immediately executable on Halin graphs once this decomposition is available.
  • The approach bypasses the explosion of reduction rules that appears in partial-k-tree methods for treewidth 4 and beyond, since it uses only the skeleton and leaf-cycle structure.
  • On instances with up to roughly a million vertices, H-TD finishes in seconds, whereas general-purpose exact solvers time out or exhaust memory and heuristics stop above width three.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The consecutive-child-interval split may transfer to other graph classes whose vertices can be arranged around a single cycle with contiguous subtrees, such as certain outerplanar or cactus-like graphs, provided a linear-time boundary-order preprocessing exists.
  • A formal correctness proof could be completed by assigning each AH-TD call a decreasing measure, for example the number of child subtrees remaining in the interval, which would simultaneously prove termination and acyclicity.
  • Because the decomposition is constructed directly rather than by reductions, a byproduct is that the same code can certify the width-three decomposition, making it usable as a practical subroutine in parameterized algorithms.
  • A natural testable extension is to run the same structural pipeline on graphs that are close to Halin, such as Halin graphs with a few extra edges, and measure the gap between the output width and the true treewidth.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper proposes H-TD, a linear-time algorithm for computing an optimal tree decomposition of Halin graphs, with optimal width three. The algorithm first recognizes the Halin decomposition via Eppstein's method, roots the skeleton, orders adjacency lists so that a DFS visits leaf-cycle leaves in cycle order, and then invokes a recursive routine AH-TD on an 'Almost Halin' subgraph. AH-TD builds a tree decomposition by splitting the subgraph into two smaller Almost Halin pieces and recursively decomposing them. The paper proves optimality and linear running time, and reports experiments against PACE 2017 solvers and libtw on generated Halin instances, claiming practical superiority on this graph class.

Significance. If the correctness proof is completed, this is a valuable practical contribution: it gives a simple, implementable, linear-time exact algorithm for an important graph class whose treewidth is known to be three, and it provides an experimental comparison against state-of-the-art solvers. The base case analysis in Appendix B is correct, and the recursive construction is plausible and elegant. The experimental evaluation is a genuine strength, including validation with the PACE validator and comparisons with both exact and heuristic competitors. However, the correctness proof currently contains two load-bearing gaps: a circular argument for the acyclicity of the recursion graph, and an unverified connectivity case in the proof of Proposition 3. These do not appear fatal to the underlying approach, but they must be repaired before the central claim can be accepted.

major comments (3)
  1. [Section 5, Corollary 1] The proof of Corollary 1 is circular as written. The corollary states that AH-TD does not cycle; its proof defines the directed graph G of recursive calls and then says 'By Corollary 1 G is a directed acyclic graph,' invoking the statement being proved. This is not acceptable as a proof. The termination argument in Proposition 2, based on recursive calls receiving strictly smaller Almost Halin subgraphs, likely supplies the missing well-founded measure, but the paper never connects that measure to acyclicity of G. Please rewrite Corollary 1 as a direct proof using the proper-subset property from Definition 8, and then use that non-circular statement in the induction of Proposition 3.
  2. [Section 5, Proposition 3, case (C3)] In the proof of Proposition 3, the first case for connectivity condition (C3) reads: 'z only appears in T (s, w, a, b). We can explicitly state that (C3) holds.' No explicit verification is provided. This is the one case that is not inherited from an invoked recursive decomposition, so it is load-bearing: without it, the constructed object is not proven to be a tree decomposition. Please add an explicit enumeration of the bags in T(s,w,a,b) for the two local patterns (i=j with h>0 and i<j), and verify for every vertex appearing only in those local bags that the set of bags containing it induces a connected subtree. In particular, check the internal bags S and A (and B when i<j) and their adjacencies to the appended recursive decompositions.
  3. [Section 5, Proposition 2] The linear-time proof states without derivation that vertex v is the root of an Almost Halin in 2(j-i+1)-1 calls and each other internal vertex u is root in 2δc(u)-1 calls. This counting is plausible, but it is asserted rather than proven, and it is needed for the linear-time claim of Proposition 4. Please provide a short inductive derivation of these counts, or at least make explicit how the recursive call structure yields them.
minor comments (3)
  1. [Section 7, footnote 1] The text says the implementation and instances 'are freely available,' but the footnote says the source code is not yet publicly released and is only available upon request. Please reconcile these statements; for a reproducibility claim, a public repository or a clear statement of availability is preferable.
  2. [Section 5, Algorithm listing] In the listing of AH-TD, the phrase 'Go to ( Step 4)' has an extra space and the step labels are inconsistent in formatting; please clean this up for readability.
  3. [Section 5, Definition 6] The notation ω2(v, j) = lcv,j,∞ is defined, but the definition of AH2(r, 1, δc(r)) excludes the edge between lr,1 and ω2(v, j); in Proposition 4 this edge is later said to be included in the bag of the first node. Please make the notation and the exclusion explicit in one place to avoid confusion.

Circularity Check

1 steps flagged · score 2.0 of 10

Corollary 1 is proved by invoking Corollary 1, but the main H-TD derivation is self-contained and not circular.

  1. other [Section 5, proof of Corollary 1 (after Proposition 2)]
    "Let G be the induced digraph of recursive calls of AH-TD. Each vertex u is a call of the algorithm and there is a directed edge u → v when call u invokes call v. By Corollary 1 G is a directed acyclic graph."

    The proof of Corollary 1 aims to show that the recursive-call digraph G is acyclic, but its only substantive inference is 'By Corollary 1 G is a directed acyclic graph.' This uses the very statement being proved as its own premise. The circularity is local rather than load-bearing: Proposition 2 already argues termination via the proper-subset measure ('strictly smaller Almost Halin'), which would imply acyclicity of the call graph, so the central H-TD claim does not reduce to a self-justifying input. Nevertheless, the proof of Corollary 1 as written is logically circular.

full rationale

The paper's central claim—that H-TD produces a width-3 tree decomposition of a Halin graph in linear time—is not circular. It is a constructive algorithm whose output was validated against the independent PACE 2017 validator, and no fitted parameter is renamed as a prediction. The only circular step I found is in the proof of Corollary 1, where acyclicity of the recursive-call graph is asserted 'By Corollary 1', i.e. by the proposition being proved. This is a genuine logical defect in the written proof, but it is readily repairable: Proposition 2's 'strictly smaller' proper-subset argument independently establishes termination, and termination plus the unconditional recursive calls rules out cycles in the call graph. A second proof gap, Proposition 3's 'We can explicitly state that (C3) holds' for vertices appearing only in T(s,w,a,b), is an omitted verification rather than a circular reduction, so it does not raise the circularity score, though it is a correctness risk. The paper's self-citations ([10], [32]) are contextual and not load-bearing. Overall, the circularity burden is low: one local circular proof step, with the central construction otherwise self-contained.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

The algorithm introduces no numerical parameters and no new mathematical entities. It relies on standard graph-theoretic facts and on two proof obligations that are currently asserted rather than demonstrated. The correctness of Eppstein's recognition algorithm is taken from the literature as an external input.

assumptions (2)
  • ad hoc to paper AH-TD's recursion graph is acyclic and thus every call eventually returns.
    Corollary 1's proof is circular ('By Corollary 1 G is a directed acyclic graph'). Termination seems to follow from the strictly-smaller Almost Halin argument in Definition 8, but the paper does not supply a valid proof of acyclicity.
  • ad hoc to paper For the local construction T(s,w,a,b), every vertex that appears only in these local bags (and not in the appended recursive decompositions) satisfies connectivity condition (C3).
    Proposition 3 states this case 'can be explicitly stated' but no explicit statement appears; Appendix B only covers the base case with no recursive calls.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Practical Linear Time Algorithm for Optimal Tree Decomposition of Halin Graphs." pith.science (2026). https://pith.science/paper/IOJXQFHD

@misc{pith2026250602346,
  author       = {Pith},
  title        = {Pith review of: A Practical Linear Time Algorithm for Optimal Tree Decomposition of Halin Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IOJXQFHD}},
  note         = {Machine review of arXiv:2506.02346}
}
abstract

This work proposes \textsc{H-Td}, a practical linear-time algorithm for computing an optimal-width tree decomposition of Halin graphs. Unlike state-of-the-art methods based on reduction rules or separators, \textsc{H-Td} exploits the structural properties of Halin graphs. Although two theoretical linear-time algorithms exist that can be applied to graphs of treewidth three, no practical implementation has been made publicly available. Furthermore, extending reduction-based approaches to partial $k$-trees with $k > 3$ results in increasingly complex rules that are challenging to implement. This motivates the exploration of alternative strategies that leverage structural insights specific to certain graph classes. Experimental validation against the winners of the Parameterized Algorithms and Computational Experiments Challenge (PACE) 2017 and the treewidth library \texttt{libtw} demonstrates the advantage of \textsc{H-Td} when the input is known to be a Halin graph.

Figures

Figures reproduced from arXiv: 2506.02346 by the authors.

Figure 1
Figure 1. A Halin graph illustrating a possible selection of vertices [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Illustration of AH1(v, i, j). The gray vertices are the representatives. In this case, AH2(v, i, j) is obtained by deleting the vertex ω1(v, j) v cv,i cv,j lc ω1(v, j) v,i,1 lcv,i+1,1 . . . . . [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. AH1(v, i, i) and AH1(v, i + 1, j) are enclosed in solid and dashed lines respectively Definition 7. For v ∈ Sk and 1 ≤ i ≤ j ≤ δc(v), we define the representatives of a well-defined AHt(v, i, j) for t ∈ {1, 2} as the set of vertices {v, lcv,i,1, ωt(v, j)}. Definition 8. For v, w ∈ Sk, 1 ≤ i ≤ j ≤ δc(v) and 1 ≤ k ≤ l ≤ δc(w), we say that a well-defined AHs(w, k, l) is strictly smaller than a well-defined AHt(v, i, j)… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Cases in which AH-TD(t, w, a, b) does not invoke any recursive call 11 [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

42 extracted references · 37 canonical work pages

  1. [1]

    Decomposition trees: structured graph representation and efficient algorithms

    Clemens Lautemann. Decomposition trees: structured graph representation and efficient algorithms. In CAAP’88: 13th Colloquium on Trees in Algebra and Programming Nancy, France, March 21–24, 1988 Proceedings 13, pages 28–39. Springer, 1988

    work page 1988

  2. [2]

    Complexity of finding embeddings in ak-tree

    Stefan Arnborg, Derek G Corneil, and Andrzej Proskurowski. Complexity of finding embeddings in ak-tree. SIAM Journal on Algebraic Discrete Methods, 8(2):277–284, 1987. 1Since the paper is currently under submission, the source code is not yet publicly released. It is available upon request. A permanent link will be provided upon publication. 8 A P REPRINT...

    work page 1987

  3. [3]

    A linear time algorithm for finding tree-decompositions of small treewidth

    Hans L Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 226–234, 1993. doi:10.1145/167088.167161

    arXiv 1993

  4. [4]

    Tree decomposition: A feasibility study

    Hein Röhrig. Tree decomposition: A feasibility study. Master’s thesis, Universität des Saarlandes, Saarbrücken, 1998. URL https://hdl.handle.net/11858/00-001M-0000-000F-3800-5

    work page 1998

  5. [5]

    Algorithms finding tree-decompositions of graphs

    Jiˇrí Matoušek and Robin Thomas. Algorithms finding tree-decompositions of graphs. Journal of Algorithms, 12(1):1–22,

    work page

  6. [6]

    Daniel P. Sanders. On linear recognition of tree-width at most four. SIAM Journal on Discrete Mathematics, 9(1):101–117,

    work page

  7. [7]

    Alexander Hein and Arie M. C. A. Koster. An experimental evaluation of treewidth at most four reductions. In Panos M. Pardalos and Steffen Rebennack, editors, Experimental Algorithms, pages 218–229, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. ISBN 978-3-642-20662-7

    work page 2011

  8. [8]

    K-packings and k-dominations on tree graphs (2004)

    M Mjelde. K-packings and k-dominations on tree graphs (2004). Chair-Pardalos, Panagote M, 2004

    work page 2004

Show all 42 references
  1. [9]

    Algorithms for minimum weighted dominating sets in cycles and cacti

    Mourad Baïou and Francisco Barahona. Algorithms for minimum weighted dominating sets in cycles and cacti. Technical report, Tech. Rep. RC25488, IBM Research, 2014

    2014

  2. [10]

    Algorithm to find a maximum 2-packing set in a cactus

    Alejandro Flores-Lamas, José Alberto Fernández-Zepeda, and Joel Antonio Trejo-Sánchez. Algorithm to find a maximum 2-packing set in a cactus. Theoretical Computer Science, 725:31–51, 2018

    2018

  3. [11]

    Algorithmic meta-theorems for restrictions of treewidth

    Michael Lampis. Algorithmic meta-theorems for restrictions of treewidth. Algorithmica, 64:19–37, 2012. doi:https://doi.org/10.1007/s00453-011-9554-x

    2012 doi

  4. [12]

    Arie M. C. A. Koster, Stan P. M. van Hoesel, and Antoon W. J. Kolen. Solving partial constraint satisfaction problems with tree decomposition. Networks, 40(3):170–180, 2002. doi:https://doi.org/10.1002/net.10046

    2002 doi

  5. [13]

    Fundamentals of parameterized complexity, volume 4

    Rodney G Downey, Michael R Fellows, et al. Fundamentals of parameterized complexity, volume 4. Springer, 2013

    2013

  6. [14]

    Improved approximation algorithms for minimum-weight vertex separators

    Uriel Feige, MohammadTaghi Hajiaghayi, and James R Lee. Improved approximation algorithms for minimum-weight vertex separators. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 563–572, 2005

    2005

  7. [15]

    Approximate tree decompositions of planar graphs in linear time

    Frank Kammer and Torsten Tholey. Approximate tree decompositions of planar graphs in linear time. Theoretical Computer Science, 645:60–90, 2016

    2016

  8. [16]

    Treelength of series–parallel graphs

    Thomas Dissaux, Guillaume Ducoffe, Nicolas Nisse, and Simon Nivelle. Treelength of series–parallel graphs. Discrete Applied Mathematics, 341:16–30, 2023

    2023

  9. [17]

    Computing bounded-width tree and branch decompositions of k-outerplanar graphs

    Ioannis Katsikarelis. Computing bounded-width tree and branch decompositions of k-outerplanar graphs. arXiv preprint arXiv:1301.5896, 2013. doi:https://doi.org/10.48550/arXiv.1301.5896

    2013 doi arXiv

  10. [18]

    Planar graphs with bounded treewidth

    Hans L Bodlaender et al. Planar graphs with bounded treewidth. 1988

    1988

  11. [19]

    The pathwidth and treewidth of cographs

    Hans L Bodlaender and Rolf H Möhring. The pathwidth and treewidth of cographs. SIAM Journal on Discrete Mathematics, 6(2):181–188, 1993

    1993

  12. [20]

    Treewidth of circular-arc graphs

    Ravi Sundaram, Karan Sher Singh, and C Pandu Rangan. Treewidth of circular-arc graphs. SIAM Journal on Discrete Mathematics, 7(4):647–655, 1994

    1994

  13. [21]

    Better algorithms for the pathwidth and treewidth of graphs

    Hans L Bodlaender and Ton Kloks. Better algorithms for the pathwidth and treewidth of graphs. InAutomata, Languages and Programming: 18th International Colloquium Madrid, Spain, July 8–12, 1991 Proceedings 18, pages 544–555. Springer,

    1991

  14. [22]

    Invitation to fixed-parameter algorithms, volume 31

    Rolf Niedermeier. Invitation to fixed-parameter algorithms, volume 31. OUP Oxford, 2006

    2006

  15. [23]

    Treelike and chordal graphs: Algorithms and generalizations

    Frank Kammer. Treelike and chordal graphs: Algorithms and generalizations. Theoretical Computer Science, 2010

    2010

  16. [24]

    doi:https://doi.org/10.1007/3-540-54233-7_162

    doi

  17. [25]

    Linear algorithms for graphs of tree-width at most four

    Daniel Preston Sanders. Linear algorithms for graphs of tree-width at most four. PhD thesis, USA, 1993. UMI Order No. GAX94-08937

    1993

  18. [26]

    Holger Dell, Thore Husfeldt, Bart M. P. Jansen, Petteri Kaski, Christian Komusiewicz, and Frances A. Rosamond. The First Parameterized Algorithms and Computational Experiments Challenge. In Jiong Guo and Danny Hermelin, editors, 11th International Symposium on Parameterized an...

    2016

  19. [27]

    Characterization and recognition of partial 3-trees

    Stefan Arnborg and Andrzej Proskurowski. Characterization and recognition of partial 3-trees. SIAM Journal on Algebraic Discrete Methods, 7(2):305–314, 1986. doi:10.1137/0607033. 9 A P REPRINT

    1986 doi

  20. [28]

    libtw, 2006

    Thomas van Dijk, Jan-Pieter van den Heuvel, and Wouter Slob. libtw, 2006. URL https://www.treewidth.com/

    2006

  21. [29]

    Bodlaender, Arie M.C.A

    Hans L. Bodlaender, Arie M.C.A. Koster, and Frank Van Den Eijkhof. PREPROCESSING RULES FOR TRIANGULA- TION OF PROBABILISTIC NETWORKS*. Computational Intelligence, 21(3):286–305, 7 2005. doi:10.1111/j.1467- 8640.2005.00274.x. URL https://doi.org/10.1111/j.1467-8640.2005.00274.x

    2005

  22. [30]

    The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration

    Holger Dell, Christian Komusiewicz, Nimrod Talmon, and Mathias Weller. The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration. In Daniel Lokshtanov and Naomi Nishimura, editors, 12th International Symposium on Parameterized and Exa...

    2017

  23. [31]

    Fomin and Dimitrios M

    Fedor V . Fomin and Dimitrios M. Thilikos. A 3-approximation for the pathwidth of halin graphs. Journal of Discrete Algorithms, 4(4):499–510, 2006. ISSN 1570-8667. doi:https://doi.org/10.1016/j.jda.2005.06.004

    2006 doi

  24. [32]

    A distributed algorithm for a maximal 2-packing set in halin graphs

    Alejandro Flores-Lamas, José Alberto Fernández-Zepeda, and Joel Antonio Trejo-Sánchez. A distributed algorithm for a maximal 2-packing set in halin graphs. Journal of Parallel and Distributed Computing, 142:62–76, 2020. ISSN 0743-7315. doi:https://doi.org/10.1016/j.jpdc.2020.03.016

    2020 doi

  25. [33]

    Studies on minimally n-connected graphs

    Rudolf Halin. Studies on minimally n-connected graphs. In Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), pages 129–136, 1971

    1969

  26. [34]

    Halin graphs and the travelling salesman problem

    Gérard Cornuéjols, Denis Naddef, and William R Pulleyblank. Halin graphs and the travelling salesman problem. Mathematical programming, 26(3):287–294, 1983. doi:https://doi.org/10.1007/BF02591867

    1983 doi

  27. [35]

    The pancyclicity of Halin graphs and their exterior contractions

    Mirosława Skowro´nska. The pancyclicity of Halin graphs and their exterior contractions. In North-Holland Mathematics Studies, volume 115, pages 179–194. Elsevier, 1985. doi:https://doi.org/10.1016/S0304-0208(08)73008-15

    1985 doi

  28. [36]

    Simple recognition of Halin graphs and their generalizations.Journal of Graph Algorithms and Applications, 20(2):323–346, 2016

    David Eppstein. Simple recognition of Halin graphs and their generalizations.Journal of Graph Algorithms and Applications, 20(2):323–346, 2016. doi:10.7155/jgaa.00395

    2016 doi

  29. [37]

    Graph theory, volume 173 of

    Reinhard Diestel. Graph theory, volume 173 of. Graduate texts in mathematics, 7, 2012

    2012

  30. [38]

    Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh

    Marek Cygan, Fedor V . Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Treewidth, pages 151–244. Springer International Publishing, Cham, 2015. ISBN 978-3-319-21275-3. doi:10.1007/978-3-319-21275-3_7. A How to compu...

    2015 doi

  31. [39]

    Lengths of cycles in halin graphs

    J Adrian Bondy and László Lovász. Lengths of cycles in halin graphs. Journal of graph theory, 9(3):397–410, 1985

    1985

  32. [42]

    To avoid invoking a recursive call, we must also ensure that h(cw,a) = 0

    applies, as we ultimately proceed to (Step 4), where T (w, a, b) is returned. To avoid invoking a recursive call, we must also ensure that h(cw,a) = 0. This condition holds only if cw,a is a leaf, which implies that cw,a = lcw,a,1. Therefore, the Almost Halin graphs for which ...

  33. [1991]

    doi:https://doi.org/10.1016/0196-6774(91)90020-Y

    ISSN 0196-6774. doi:https://doi.org/10.1016/0196-6774(91)90020-Y

    doi

  34. [1996]

    doi:10.1137/S0895480193243043

    doi

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.