强细树的多项式时间构造
A polynomial-time construction of strong thin trees
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
该稿件研究有限多重图中强细树的构造算法。作者声称给出强细树的确定性多项式时间构造：对至少一个顶点上的有限k边连通无环多重图，算法构造一棵生成树，使每个割至多包含其C/k比例的边，C为通用常数；运行时间对二进制输入长度（含平行边重数用二进制编码）为多项式。该结果若成立，将把强细树的存在性推进为有效构造。但手稿为AI产生，未经独立审查或同行评议。
- 作者声称给出强细树的确定性多项式时间构造算法。
- 生成树在每个割中至多占C/k比例的边，C为通用常数。
- 运行时间对二进制输入长度为多项式，含平行边重数二进制编码。
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
We give a deterministic polynomial-time construction of strong thin trees. Given a finite k-edge-connected loopless multigraph on at least one vertex, the algorithm constructs a spanning tree meeting every cut in at most a $`C/k`$ fraction of its edges, for a universal constant C. The running time is polynomial in the binary input length, including when parallel-edge multiplicities are encoded in binary.
用户标记：未标记
固定编号：4299d35895804670
原文来源