论文标题
通过重要削减解决路线问题
Solving Routing Problems via Important Cuts
论文作者
论文摘要
我们介绍了一种使用重要削减的新方法，使我们能够在以下路由问题上设计明显更快的固定参数可容纳算法（FPT）算法：中国邮政问题混合了有向边数的参数（Gutin等人，JCSS，JCSS 2017），JCSS 2017，2017年，最小共享边缘问题（MSSE）参数（MSSE）参数（MSSE）参数是两种指定的路径（fl sevief）。 JCSS 2019）和加权最小的预防问题（Gruttemeier等，WG 2021）。最小脆弱性问题（MV）是MSE的概括（Assadi等，算法，2014）。通过P参数化的MV（与MSE相同的参数）的唯一已知的FPT算法是弦图（Aoki等，JCO 2018）。我们为所有无向图上的MV设计了FPT算法。
We introduce a novel approach of using important cuts which allowed us to design significantly faster fixed-parameter tractable (FPT) algorithms for the following routing problems: the Mixed Chinese Postman Problem parameterized by the number of directed edges (Gutin et al., JCSS 2017), the Minimum Shared Edges problem (MSE) parameterized by the number p of paths between two specified vertices (Fluschnik et al., JCSS 2019), and the Weighted Min Cut Prevention problem (Gruttemeier et al., WG 2021). The Minimum Vulnerability problem (MV) is a generalization of MSE (Assadi et al., Algorithmica 2014). The only known FPT algorithm for MV parameterized by p (the same parameter as for MSE) was for chordal graphs (Aoki et al., JCO 2018). We design an FPT algorithm for MV on all undirected graphs.
