Skip to content
DraconiticResearch
Search Sources API
182,469 studies31 sourcesUpdated 32 min ago
PreprintarXiv licencearXiv

Combinatorial Algorithms for Partial Inverse Min-Max Spanning Tree Problem under the Weighted Sum Hamming Distance

  • Qingzhen Dong
  • Xianyue Li
  • Xiaowen Kong
Open at sourcePDFDOICite

Abstract

Given a connected weighted graph G=(V, E, w) and a forest F of G, the goal of partial inverse min-max spanning tree problem is to change the weight function as little as possible, so that there is a min-max spanning tree with respect to the new weight function containing F. In this paper, we study this problem under the weighted sum Hamming distance. We take the alternative set of the maximum edge weight in F with respect to the optimal weight function as a key factor, and further consider the case of this problem under the restriction of this factor. On this basis, a polynomial time algorithm with time complexity O(|V|^4) is proposed to solve this problem.

Related

  1. Some results on the distance spectral radius and edge-disjoint spanning trees of graphs
    Yongbin Gao, Ligong Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Identifying critical risk factors in railway operations based on directed weighted complex networks and combinatorial weighting-TOPSIS
    Guanyi Liu, Xuewei Li, Rui Yang
    PLOS OnePeer-reviewedCC BY 4.0Full textAlgebra & number theoryGeometry & topologyPLOS
  3. Insdel Decoding Algorithms for Maximum Distance Separable Codes
    Bencheng Fan, Margreta Kuijper, Jingge Zhu
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  4. On the partial convexification for low-rank spectral optimization: rank bounds and algorithms
    Yongchun Li, Weijun Xie
    Mathematical ProgrammingPeer-reviewedCC BYFull textOptimisation & controlHAL
  5. Distance statistics of block-weighted planar quadrangulations
    Jérémie Bouttier, Emmanuel Guitter, Hugo Manet
    HALPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsProbabilityHALarXiv

Cite

BibTeXRIS
BibTeX
@misc{dong2026combinatorial,
  title = {{Combinatorial Algorithms for Partial Inverse Min-Max Spanning Tree Problem under the Weighted Sum Hamming Distance}},
  author = {Qingzhen Dong and Xianyue Li and Xiaowen Kong},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.00094},
  eprint = {2611.00094},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.00094},
}
RIS
TY  - UNPB
TI  - Combinatorial Algorithms for Partial Inverse Min-Max Spanning Tree Problem under the Weighted Sum Hamming Distance
AU  - Qingzhen Dong
AU  - Xianyue Li
AU  - Xiaowen Kong
PY  - 2026
DA  - 2026/11/01
PB  - arXiv
DO  - 10.48550/arxiv.2611.00094
UR  - https://arxiv.org/abs/2611.00094
AB  - Given a connected weighted graph G=(V, E, w) and a forest F of G, the goal of partial inverse min-max spanning tree problem is to change the weight function as little as possible, so that there is a min-max spanning tree with respect to the new weight function containing F. In this paper, we study this problem under the weighted sum Hamming distance. We take the alternative set of the maximum edge weight in F with respect to the optimal weight function as a key factor, and further consider the case of this problem under the restriction of this factor. On this basis, a polynomial time algorithm with time complexity O(|V|^4) is proposed to solve this problem.
ER  -