论文标题
寻找各种各样的树木，路径等
Finding Diverse Trees, Paths, and More
论文作者
论文摘要
数学建模是一种解决许多现实世界问题的标准方法，解决方案的{\ em多样性}是一个重要的问题，在应用从数学模型获得的解决方案中出现到现实世界中的问题。许多研究致力于寻找多种解决方案。 Baste等。 （算法2019，IJCAI 2020年）最近从固定参数障碍性的角度开始了对组合问题的各种解决方案的研究。他们考虑了找到$ r $解决方案的问题，这些解决方案可以最大程度地提高一些多样性度量（它们之间的成对锤击距离的最小或总和），并为多种著名问题的多元化版本提供了一些固定参数可访问的算法，例如{\ sc vertex cover}，例如{\ sc vertex cover}，{\ sc sc $ sc $ sc $ sc $ d $ d $ - 图。在这项工作中，我们研究了（固定参数）的（固定参数）障碍，这些问题是找到各种跨越树木，路径和几个子图的问题。特别是，我们表明，给定图形$ g $和一个整数$ r $，计算$ r $跨度的$ g $的问题可以在多项式时间内解决最大化的成对锤距的总和。据作者所知，这是第一个可以找到无限尺寸的解决方案的多项式解决案例。
Mathematical modeling is a standard approach to solve many real-world problems and {\em diversity} of solutions is an important issue, emerging in applying solutions obtained from mathematical models to real-world problems. Many studies have been devoted to finding diverse solutions. Baste et al. (Algorithms 2019, IJCAI 2020) recently initiated the study of computing diverse solutions of combinatorial problems from the perspective of fixed-parameter tractability. They considered problems of finding $r$ solutions that maximize some diversity measures (the minimum or sum of the pairwise Hamming distances among them) and gave some fixed-parameter tractable algorithms for the diverse version of several well-known problems, such as {\sc Vertex Cover}, {\sc Feedback Vertex Set}, {\sc $d$-Hitting Set}, and problems on bounded-treewidth graphs. In this work, we investigate the (fixed-parameter) tractability of problems of finding diverse spanning trees, paths, and several subgraphs. In particular, we show that, given a graph $G$ and an integer $r$, the problem of computing $r$ spanning trees of $G$ maximizing the sum of the pairwise Hamming distances among them can be solved in polynomial time. To the best of the authors' knowledge, this is the first polynomial-time solvable case for finding diverse solutions of unbounded size.
