论文标题
列举（在）有限维posets的（IN）可比性图中列举最小的主导集
Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
论文作者
论文摘要
在超图中列举最小横向是一个众所周知的困难问题。可以将其简化为列举图表中的最小主导集，实际上甚至是在无与伦比的图中列举最小的主导集。我们为基础POSET具有界限的无与伦比图提供了输出多项式时间算法。通过不同的证明技术，我们还为它们的补充提供了一种输出多项式算法，即用于有界维posets的可比性图。 我们用于无与伦比图的算法基于手电筒搜索，并依赖于Golumbic等人给出的具有界限的无与伦比图的几何表示。 1983年。它以多项式延迟运行，只需要多项式空间。我们的可比性图算法基于Golovach等人引入的翻转方法。在2015年。它以渐进的多项式时间进行，需要指数空间。 此外，我们还展示了如何改进翻转方法，以便仅需要多项式空间。由于翻转方法是在许多图类中列举最小的主导集的最知名算法的关键工具，因此这可以直接改进最新的技术。
Enumerating minimal transversals in a hypergraph is a notoriously hard problem. It can be reduced to enumerating minimal dominating sets in a graph, in fact even to enumerating minimal dominating sets in an incomparability graph. We provide an output-polynomial time algorithm for incomparability graphs whose underlying posets have bounded dimension. Through a different proof technique, we also provide an output-polynomial algorithm for their complements, i.e., for comparability graphs of bounded dimension posets. Our algorithm for incomparability graphs is based on flashlight search and relies on the geometrical representation of incomparability graphs with bounded dimension, as given by Golumbic et al. in 1983. It runs with polynomial delay and only needs polynomial space. Our algorithm for comparability graphs is based on the flipping method introduced by Golovach et al. in 2015. It performs in incremental-polynomial time and requires exponential space. In addition, we show how to improve the flipping method so that it requires only polynomial space. Since the flipping method is a key tool for the best known algorithms enumerating minimal dominating sets in a number of graph classes, this yields direct improvements on the state of the art.
