多样化的收藏在matroids和图表中.
Fedor V Fomin1, Petr A Golovach1, Fahad Panolan2
1University of Bergen, Bergen, Norway.
概括
本研究探讨了寻找各种解决方案的参数化复杂性,用于组合问题,如加权的各种基础和各种完美匹配. 我们开发了固定参数可处理算法,在解决方案多样性是关键参数时提供高效的解决方案.
科学领域:
- 离散的数学 离散的数学
- 理论计算机科学 理论计算机科学
- 组合优化的优化.
背景情况:
- 组合式问题通常涉及到在数学对象中找到特定的结构.
- 这些问题的复杂性可以使用参数化的复杂性来分析,专注于特定的输入参数.
- 在需要多个不同的选项的应用中,多种解决方案至关重要.
研究的目的:
- 为了研究三个基本的组合学问题的参数复杂性:加权的多种基础,加权的多种常见独立集和多种完美匹配.
- 通过所需的多样化解决方案数量进行参数化时,确定这些问题是否可计算处理.
- 开发高效的算法和数据结构,以找到各种解决方案.
主要方法:
- 使用参数化复杂性分析,重点关注参数k (解决方案数).
- 固定参数可处理 (FPT) 算法被设计为三个问题中的每一个.
- 用一个核心化技术来导出一个多项式大小的核心,用于加权多种基数问题.
主要成果:
- 证明没有一个研究的问题可以在多项式时间内解决,除非P=NP.
- 为所有三个问题开发了固定的参数可处理算法,复杂性多项取决于k.
- 建立了一个与k相关的大小的内核,用于加权多种基数问题,表示结构性质.
结论:
- 寻找多种基础,共同的独立集合和完美的匹配的问题通常是很难计算的.
- 参数化的复杂性提供了一个可行的方法来有效地解决这些问题,当解决方案的数量 (k) 是小.
- 衍生出来的FPT算法和内核为各种解决方案的寻找提供了理论上的保证和实际的含义.
相关概念视频
Vector Algebra: Graphical Method
Vectors can be multiplied by scalars, added to other vectors, or subtracted from other vectors. The vector sum of two (or more) vectors is called the resultant vector or, for short, the resultant.
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
Theorems of Pappus and Guldinus: Problem Solving
Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a cylinder...
SFG Algebra
In Signal Flow Graph (SFG) algebra, the value a node represents is determined by the sum of all signals entering that node. This summed value is then transmitted through every branch leaving the node, making the SFG a powerful tool for visualizing and analyzing control systems.
Each node in an SFG corresponds to a variable, and the interactions between nodes are represented by branches with associated gains. When multiple branches lead into a node, the value at that node is the sum of the...
Each node in an SFG corresponds to a variable, and the interactions between nodes are represented by branches with associated gains. When multiple branches lead into a node, the value at that node is the sum of the...
Graphs of Equations in Two Variables
An equation with two variables, typically written in the form y = f(x) or Ax + By = C, describes a relationship between quantities represented by x and y. Each solution to such an equation is an ordered pair (x, y) that satisfies the equation when substituted. These pairs can be represented graphically to understand the variables' relationship visually.A common technique for constructing the graph of a two-variable equation is to create a value table. Begin by choosing several values for the...
Graphs of Functions
Graphs of functions provide a visual representation of how output values change in response to varying inputs. Each point on the graph corresponds to an ordered pair, where the x-coordinate (independent variable) determines the horizontal position and the y-coordinate (dependent variable) determines the vertical position. Linear functions like y = x give a straight line, indicating a constant rate of change.Nonlinear functions display more complex behaviors. Even power functions generate...
Graphical Representation of Inequalities
The graph of the equation where y equals x squared forms a curve known as a parabola. This curve acts as a boundary in the coordinate plane, dividing it into distinct regions based on the relative position of points.When the equality sign in the equation is replaced with an inequality—such as greater than, less than, greater than or equal to, or less than or equal to—the graphical representation changes from a single curve into a broader shaded area that signifies the set of all points...


