The role of graph width metrics, such as treewidth, pathwidth, and cliquewidth, is now seen as central in both algorithm design and the delineation of what is algorithmically possible. In this article we introduce a new, related, parameter for graphs, persistence.A path decomposition of width k, in which every vertex of the underlying graph belongs to at most l nodes of the path, has pathwidth k and persistence l, and a graph that admits such a decomposition has bounded persistence pathwidth.We believe that this natural notion truly captures the intuition behind the notion of pathwidth. We present some basic results regarding the general recognition of graphs having bounded persistence path decompositions.
展开▼
机译：图形宽度度量（如树宽，路径和Cliquewdth）的角色现在被视为算法设计中的中心，并且删除算法是可能的。在本文中，我们介绍一个新的，相关的参数持久性。宽度 k的路径分解，其中底层图的每个顶点都属于最多< i> l 路径的节点，具有路径 k 和持久性l，以及承认这种分解的图表具有界限持久性路径。< / i>我们认为这种自然概念真正捕捉到路径概念背后的直觉。我们对具有有界持久路径分解的图表的总体识别提供了一些基本结果。
展开▼
