A Win/Win Algorithm for the $$(k+1) $$ -LST/ $$k $$ -Pathwidth Problem
Tóm tắt
We describe a Win/Win algorithm that produces in time polynomial in the size of
a graph
$$G
$$
and a given parameter
$$k
$$
either a spanning tree with at least
$$k+1
$$
leaves or a path decomposition of width at most
$$k
$$
. This algorithm is optimal due to the path
decomposition theorem.
Tài liệu tham khảo
D. Bienstock, N. Robertson, P. D. Seymour, and R. Thomas, “Quickly Excluding a Forest,” J. Comb. Theory, Ser. B, 52, 274–283 (1991).
R. J. Douglas, “NP-Completeness and Degree Restricted Spanning Trees,” Discrete Math. 105 (1-3), 41–47 (1992).
T. Kashiwabara and T. Fujisawa, “NP-Completeness of the Problem of Finding a Minimum-Clique-Number Interval Graph Containing a Given Graph as a subgraph,” in Proceedings. 1979 International Symposium on Circuits and Systems (Tokyo, Japan, July 17–19, 1979) (IEEE, New York, 1979), pp. 657–660.
H. L. Bodlaender, E. D. Demaine, M. R. Fellows, et al. Open Problems in Parameterized and Exact Computation—IWPEC 2008 . Techn. Rep. UU–CS–2008–017 (Utrecht Univ., Utrecht, 2008). Available at http://www.cs.uu.nl/research/techreps/repo/CS-2008/2008-017.pdf (accessed Aug. 3, 2021).
R. Diestel, “Graph Minors I: A Short Proof of the Path-Width Theorem,” Comb. Prob. Comput. 4 (1), 27–30 (1995).