Enumeration of Support-Closed Subsets in Confluent Systems
Enumeration of Support-Closed Subsets in Confluent Systems
复制标题
DOI：
10.1007/s00453-022-00927-x
复制
发表时间：
2022-01
期刊：
影响因子：
1.1
通讯作者：
Kazuya Haraguchi;H. Nagamochi
中科院分区：
文献类型：
--
作者：
Kazuya Haraguchi;H. Nagamochi
对于一个有限元素集V，合流系统是一个集合系统，使得每三个集合都蕴含，这里我们称之为一个集合成分。我们假设两个预言机和是可用的，其中给定两个子集，返回一个最大分量;给定一个集合，返回所有最大分量。给定合流系统中的一个项集I和一个函数，如果C中的公共项集是包含最大的，则称为解（或支持闭）;即，for any component组件with.我们证明了存在一个算法，在多项式延迟和多项式空间中枚举所有的解决方案。所提出的算法产生用于枚举属性图中的连接器的多项式延迟和多项式空间算法（即，使得每个顶点被分配项的图），以及用于枚举具有各种类型的连通性的所有子图，诸如对于固定边k的给定无向/有向图中的所有边/顶点连通的导出子图和所有边/顶点连通的生成子图。
For a finite setVof elements, aconfluent systemis a set systemsuch that every three setswithimplies, where we call a setacomponent. We assume that two oraclesandare available, where given two subsets,returns a maximal componentwith; and given a set,returns all maximal componentswith. Given a setIof items and a functionin a confluent system, a componentis called asolution(orsupport-closed) if the set of common items inCis inclusively maximal; i.e.,for any componentwith. We prove that there exists an algorithm of enumerating all solutions in polynomial delay and in polynomial space. The proposed algorithm yields polynomial-delay and polynomial-space algorithms for enumerating connectors in an attributed graph (i.e., a graph such that each vertex is assigned items) and for enumerating all subgraphs with various types of connectivities such as allk-edge/vertex-connected induced subgraphs and allk-edge/vertex-connected spanning subgraphs in a given undirected/directed graph for a fixedk.