检索结果-内蒙古大学图书馆

enumeration. algorithms for minimal siphons in Petri nets based on place constraints

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART A-SYSTEMS AND HUMANS 2005年第6期35卷 844-854页

作者： Cordone, R Ferrarini, L Piroddi, L Univ Milan Dipartimento Tecnol Informaz Polo Didattico Ric Crema I-26013 Crema Italy Politecn Milan Dipartimento Elettr & Informaz I-20133 Milan Italy

The paper addresses the problem of enumerating minimal siphons in an ordinary Petri net. The algorithms developed in this work recursively use a problem partitioning procedure to reduce the original search problem to multiple simpler search subproblems. Each subproblem has specific additional place constraints with respect to the original problem. Some results on algorithm correctness, convergence, and computational complexity are provided, as well as an experimental evaluation of performance. The algorithms can be applied to enumerate minimal, place-minimal siphons, or even siphons that are minimal with respect to given subsets of places.

关键词： deadlock avoidance enumeration algorithms Petri nets (PNs) siphons

来源：评论

学校读者我要写书评

暂无评论

Maximization of submodular functions: Theory and enumeration algorithms

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2009年第1期198卷 102-112页

作者： Goldengorin, Boris Univ Groningen Dept Operat NL-9700 AV Groningen Netherlands

Submodular functions are powerful tools to model and solve either to optimality or approximately many operational research problems including problems defined on graphs. After reviewing some long-standing theoretical results about the structure of local and global maxima of submodular functions, Cherenin's selection rules and his Dichotomy Algorithm, we revise the above mentioned theory and show that our revision is useful for creating new non-binary branching algorithms and finding either approximation solutions with guaranteed accuracy or exact ones. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Maximization Submodular functions enumeration algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient enumeration of transversal edge-partitions

引用

DISCRETE APPLIED MATHEMATICS 2025年 361卷 276-287页

作者： Shinraku, Koki Yamanaka, Katsuhisa Hirayama, Takashi Iwate Univ Fac Sci & Engn Ueda 4-3-5 Morioka Iwate Japan

An irreducible triangulation is a plane graph such that its outer face is a quadrangle, every inner face is a triangle, and it has no separating triangle. Let T be an irreducible triangulation with n vertices. A rectangular dual R of T is a dissection of a rectangle into (small) rectangles such that (1) each rectangle of R corresponds to a vertex of T , and (2) two rectangles of R are adjacent if the two corresponding vertices of T are adjacent. Finding a rectangular dual of a given graph has an application on cartograms and VLSI floor-planning. In this paper, we consider the problem of enumerating all the rectangular duals of a given irreducible triangulation. It is known that the set of rectangular duals of an irreducible triangulation T one-to-one corresponds to the set of transversal edge-partitions of T . Hence, in this paper, we design an enumeration algorithm of all the transversal edge-partitions of an irreducible triangulation with n vertices. The proposed algorithm enumerates them in O ( n )-delay and O ( n 2 )-space after O ( n log n )-time preprocessing. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： enumeration algorithms Plane graphs Irreducible triangulations Rectangular duals Transversal edge-partitions

来源：评论

学校读者我要写书评

暂无评论

Sublinear-Space and Bounded-Delay algorithms for Maximal Clique enumeration in Graphs

引用

ALGORITHMICA 2020年第6期82卷 1547-1573页

作者： Conte, Alessio Grossi, Roberto Marino, Andrea Versari, Luca Univ Pisa Dipartimento Informat Pisa Italy Univ Firenze Florence Italy

Due to the sheer size of real-world networks, delay and space have become quite relevant measures of the cost of enumerating patterns for network analytics. This paper presents efficient algorithms for listing maximal... 详细信息

关键词： enumeration algorithms Maximal cliques Network mining and analytics Reverse search Space efficiency Polynomial time delay

来源：评论

学校读者我要写书评

暂无评论

Minimal dominating sets in graph classes: Combinatorial bounds and enumeration

引用

THEORETICAL COMPUTER SCIENCE 2013年 487卷 82-94页

作者： Couturier, Jean-Francois Heggernes, Pinar van 't Hof, Pim Kratsch, Dieter Univ Lorraine LITA F-57045 Metz 01 France Univ Bergen Dept Informat N-5020 Bergen Norway

The number of minimal dominating sets that a graph on n vertices can have is known to be at most 1.7159(n). This upper bound might not be tight, since no examples of graphs with 1.5705(n) or more minimal dominating sets are known. For several classes of graphs, we substantially improve the upper bound on the number of minimal dominating sets. At the same time, we give algorithms for enumerating all minimal dominating sets, where the running time of each algorithm is within a polynomial factor of the proved upper bound for the graph class in question. In several cases, we provide examples of graphs containing the maximum possible number of minimal dominating sets for graphs in that class, thereby showing the corresponding upper bounds to be tight. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Minimal dominating sets enumeration algorithms Combinatorial bounds Graph classes

来源：评论

学校读者我要写书评

暂无评论

Randomised enumeration of Small Witnesses Using a Decision Oracle

引用

ALGORITHMICA 2019年第2期81卷 519-540页

作者： Meeks, Kitty Univ Glasgow Sch Comp Sci Sir Alwyn Williams Bldg Glasgow G12 8RZ Lanark Scotland

Many combinatorial problems involve determining whether a universe of n elements contains a witness consisting of k elements which have some specified property. In this paper we investigate the relationship between the decision and enumeration versions of such problems: efficient methods are known for transforming a decision algorithm into a search procedure that finds a single witness, but even finding a second witness is not so straightforward in general. We show that, if the decision version of the problem can be solved in time f(k) . poly(n), there is a randomised algorithm which enumerates all witnesses in time e(k+o(k)) . f(k) . poly(n) . N, where N is the total number of witnesses. If the decision version of the problem is solved by a randomised algorithm which may return false negatives, then the same method allows us to output a list of witnesses in which any given witness will be included with high probability. The enumeration algorithm also gives rise to an efficient algorithm to count the total number of witnesses when this number is small.

关键词： enumeration algorithms Parameterized complexity Randomized algorithms Approximate enumeration Color coding

来源：评论

学校读者我要写书评

暂无评论

enumeration aspects of maximal cliques and bicliques

引用

DISCRETE APPLIED MATHEMATICS 2009年第7期157卷 1447-1459页

作者： Gely, Alain Nourine, Lhouari Sadi, Bachir Univ Blaise Pascal LIMOS F-63173 Aubiere France

We present a general framework to study enumeration algorithms for maximal cliques and maximal bicliques of a graph. Given a graph G, we introduce the notion of the transition graph T(G) whose vertices are maximal cliques of G and arcs are transitions between cliques. We show that T(G) is a strongly connected graph and characterize a rooted cover tree of T(G) which appears implicitly in [D.S. Johnson, M. Yannakakis, C.H. Papadimitriou, On generating all maximal independent sets, Information Processing Letters 27 (1988) 119-123;S. Tsukiyama, M. Ide, M. Aiyoshi, I. Shirawaka, A new algorithm for generating all the independent sets, SIAM journal on Computing 6 (1977) 505-517]. When G is a bipartite graph, we show that the Galois lattice of G is a partial graph of T(G) and we deduce that algorithms based on the Galois lattice are a particular search of T(G). Moreover, we show that algorithms in [G. Alexe, S. Alexe, Y. Crama, S. Foldes, P.L. Hammer, B. Simeone, Consensus algorithms for the generation of all maximal bicliques, Discrete Applied Mathematics 145 (1) (2004) 11-21: L Nourine, O. Raynaud, A fast algorithm for building lattices, Information Processing Letters 71 (1999) 199-204] generate maximal bicliques of a bipartite graph in O(n(2)) per maximal biclique, where n is the number of vertices in G. Finally, we show that under some specific numbering, the transition graph T(G) has a hamiltonian path for chordal and comparability graphs. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Maximal cliques Maximal bicliques Lattice enumeration algorithms

来源：评论

学校读者我要写书评

暂无评论

Streaming enumeration on Nested Documents

引用

ACM TRANSACTIONS ON DATABASE SYSTEMS 2024年第4期49卷 1-39页

作者： Munoz, Martin Riveros, Cristian Pontificia Univ Catolica Chile Santiago Chile Millennium Inst Fdn Res Data Santiago Chile Pontificia Univ Catolica Chile Sch Engn Dept Comp Sci Santiago Chile

Some of the most relevant document schemas used online, such as XML and JSON, have a nested format. In the past decade, the task of extracting data from nested documents over streams has become especially relevant. We focus on the streaming evaluation of queries with outputs of varied sizes over nested documents. We model queries of this kind as Visibly Pushdown Annotators (VPAnn), a computational model that extends visibly pushdown automata with outputs and has the same expressive power as monadic second-order logic over nested documents. Since processing a document through a VPAnn can generate a massive number of results, we are interested in reading the input in a streaming fashion and enumerating the outputs one after another as efficiently as possible, namely, with constant delay. This article presents an algorithm that enumerates these elements with constant delay after processing the document stream in a single pass. Furthermore, we show that this algorithm is worst-case optimal in terms of update-time per symbol and memory usage.

关键词： Streaming nested documents query evaluation enumeration algorithms

来源：评论

学校读者我要写书评

暂无评论

Algorithmic enumeration of surrounding polygons

引用

DISCRETE APPLIED MATHEMATICS 2021年 303卷 305-313页

作者： Yamanaka, Katsuhisa Avis, David Horiyama, Takashi Okamoto, Yoshio Uehara, Ryuhei Yamauchi, Tanami Iwate Univ Morioka Iwate Japan McGill Univ Montreal PQ Canada Kyoto Univ Kyoto Japan Hokkaido Univ Sapporo Hokkaido Japan Univ Electrocommun Chofu Tokyo Japan RIKEN Ctr Adv Intelligence Project Tokyo Japan Japan Adv Inst Sci & Technol Nomi Japan

We are given a set S of points in the Euclidean plane. We assume that S is in general position. A simple polygon P is a surrounding polygon of S if each vertex of P is a point in S and every point in S is either inside P or a vertex of P. In this paper, we present an enumeration algorithm of the surrounding polygons for a given point set. Our algorithm is based on reverse search by Avis and Fukuda and enumerates all the surrounding polygons in polynomial delay and quadratic space. It also provides the first space efficient method to generate all simple polygonizations on a given point set in exponential time. By relating these two problems we provide an upper bound on the number of surrounding polygons. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Polygons Surrounding polygons Simple polygonizations enumeration algorithms Polynomial delay

来源：评论

学校读者我要写书评

暂无评论

Maximal Irredundant Set enumeration in Bounded-Degeneracy and Bounded-Degree Hypergraphs 1

引用

30th International Workshop on Combinatorial algorithms (IWOCA)

作者： Conte, Alessio Kante, Mamadou Moustapha Marino, Andrea Uno, Takeaki Natl Inst Informat Tokyo Japan Univ Pisa Pisa Italy Univ Clermont Auvergne CNRS LIMOS Aubiere France Univ Florence Florence Italy

ISBN: (数字)9783030250058

ISBN: (纸本)9783030250041;9783030250058

An irredundant set of a hypergraph G = (V, H) is a subset S of its nodes such that removing any node from S decreases the number of hyperedges it intersects. The concept is deeply related to that of dominating sets, as the minimal dominating sets of a graph correspond exactly to the dominating sets which are also maximal irredundant sets. In this paper we propose an FPT-delay algorithm for listing maximal irredundant sets, whose delay is O(2(d)Delta(d+1)n(2)), where d is the degeneracy of the hypergraph and. the maximum node degree. As d <= Delta, we immediately obtain an algorithm with delay O(2(Delta)Delta(Delta+1)n(2)) that is FPT for bounded-degree hypergraphs. This result opens a gap between known bounds for this problem and those for listing minimal dominating sets in these classes of hypergraphs, as the known running times used to be the same, hinting at the idea that the latter may indeed be harder.

关键词： Irredundant sets enumeration algorithms FPT Polynomial delay

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：