Graph Coloring Lower Bounds from Decision Diagrams
Graph Coloring Lower Bounds from Decision Diagrams
复制标题
决策图中的图形着色下界
DOI：
10.1007/978-3-030-45771-6_31
复制
发表时间：
2020
影响因子：
6.3
通讯作者：
W. V. Hoeve
中科院分区：
文献类型：
--
作者：
W. V. Hoeve
我们介绍了一个计算图着色问题下界的迭代框架。我们使用松弛决策图来紧凑地表示颜色类的指数集，或独立集，其中一些可能包含边冲突。我们的程序使用最小网络流模型来计算着色数的下界并识别冲突。与这些冲突相关联的不可行颜色类通过细化决策图来删除。我们证明，在最好的情况下，我们的方法可以使用比精确图小得多的图来证明最优性。我们还提供了一个基准实例的实验评估，并报告了一个开放实例的改进下界。
We introduce an iterative framework for computing lower bounds to graph coloring problems. We utilize relaxed decision diagrams to compactly represent an exponential set of color classes, or independent sets, some of which may contain edge conflicts. Our procedure uses minimum network flow models to compute lower bounds on the coloring number and identify conflicts. Infeasible color classes associated with these conflicts are removed by refining the decision diagram. We prove that in the best case, our approach may use exponentially smaller diagrams than exact diagrams for proving optimality. We also provide an experimental evaluation on benchmark instances, and report an improved lower bound for one open instance.
DOI：
10.1007/978-3-319-77404-6_47
发表时间：
2017-06
期刊：
--
影响因子：
--
作者：
Adalat Jabrayilov;Petra Mutzel
通讯作者：
Adalat Jabrayilov;Petra Mutzel