机构名称：
¥ 4.0
参数化的复杂性。已知许多广泛关注的计算问题通常是NP -HARD。然而，通常可以使用隐式的许多现实实例来有效地找到确切的解决方案。在特定类别的各种实例上，对各种问题进行了长期的系统研究，并且朝这个方向进行研究构成了计算机科学的基本领域之一。但是，在许多现实情况下，不可能定义我们希望解决的明确类别的实例；实例不像是黑白（是否属于特定类别），而是具有各种灰色阴影（具有一定程度的内部结构）。相对年轻的参数化复杂性范式[6，4，8，16]提供了处理这种情况的理想工具。在参数化设置中，我们将每个实例与数值参数相关联，该参数捕获了该实例的“结构化”。这样就可以开发其性能的算法强烈取决于参数 - 而不是经典设置，在这种情况下，我们经常将拖延性与多项式运行时间相关联，而棘手的性能与超多种元素相关联，参数化算法自然而然地“缩放”与实例中包含的结构量相关联。参数化设置中的易处理性的中心概念是固定参数的拖延（简而言之），这意味着可以通过f（k）·n o（k）·n o（1）的运行时解决给定的问题（f是任意可计算的功能，k是k的值，k是k的值，k是参数的值，n是输入大小）。除了固定参数障碍性外，参数化的复杂性景观还包括各种伴侣概念，例如XP索取性，内核化和W- hardness。
图形图中的参数化复杂性 - 滴
主要关键词
相关文件推荐
