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

Efficient enumeration of Flat-Foldable Single Vertex Crease Patterns

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2019年第3期E102D卷 416-422页

作者： Ouchi, Koji Uehara, Ryuhei Japan Adv Inst Sci & Technol Sch Informat Sci Nomi 9231292 Japan

We investigate enumeration of distinct flat-foldable crease patterns under the following assumptions: positive integer n is given;every pattern is composed of n lines incident to the center of a sheet of paper;every angle between adjacent lines is equal to 2 pi/n;every line is assigned one of "mountain," "valley," and "flat (or consequently unfolded)";crease patterns are considered to be equivalent if they are equal up to rotation and reflection. In this natural problem, we can use two well-known theorems for flat-foldability: the Kawasaki Theorem and the Maekawa Theorem in computational origami. Unfortunately, however, they are not enough to characterize all flat-foldable crease patterns. Therefore, so far, we have to enumerate and check flat-foldability one by one using computer. In this study, we develop the first algorithm for the above stated problem by combining these results in a nontrivial way and show its analysis of efficiency.

关键词： computational origami enumeration algorithm flat foldability Kawasaki theorem Maekawa theorem

来源：评论

学校读者我要写书评

暂无评论

Face pairing graphs and 3-manifold enumeration

引用

JOURNAL OF KNOT THEORY AND ITS RAMIFICATIONS 2004年第8期13卷 1057-1101页

作者： Burton, BA Univ Melbourne Dept Math & Stat Parkville Vic 3010 Australia

The face pairing graph of a 3-manifold triangulation is a 4-valent graph denoting which tetrahedron faces are identified with which others. We present a series of properties that must be satisfied by the face pairing graph of a closed minimal P-2-irreducible triangulation. In addition we present constraints upon the combinatorial structure of such a triangulation that can be deduced from its face pairing graph. These results are then applied to the enumeration of closed minimal P-2-irreducible 3-manifold triangulations, leading to a significant improvement in the performance of the enumeration algorithm. Results are offered for both orientable and non-orientable triangulations.

关键词： minimal triangulation census enumeration algorithm face pairing graph

来源：评论

学校读者我要写书评

暂无评论

A Recursive Approach for Maximal (Δ, γ)-Clique enumeration in Temporal Networks 28th

A Recursive Approach for Maximal (Δ, γ)-Clique Enumeration...

引用

28th European Conference on Advances in Databases and Information Systems (ADBIS)

作者： Pal, Bithika Indian Inst Technol Kharagpur Dept Comp Sci & Engn Kharagpur 721302 W Bengal India

ISBN: (纸本)9783031706288;9783031706264

A set of objects and a binary relation among them is often represented by a graph or network. Most of the networks that we deal with in practice (e.g., social networks, human contact networks, financial transaction networks, etc.) are time-varying in nature, i.e., the relationship changes over time. Such networks are often modeled as Temporal Networks. In this paper, we study the problem of enumerating cohesive sub-structures present in a given temporal network. We call such substructure as (Delta, gamma)-clique, which is a tuple of vertex subset and time interval, such that every pair of vertices in the vertex subset has at least gamma edges in every Delta duration of the time interval. We propose a recursive solution approach to enumerate all the maximal (Delta, gamma)-cliques. The proposed approach is divided into two parts. First, it initializes all the cliques of size 2 with maximum duration satisfying the (Delta, gamma)-clique property, and recursively, adds vertices till it becomes maximal. The correctness of the proposed method has been established, and the complexity analysis has also been done. Several experiments are carried out using real-world temporal network datasets to highlight the efficiency of the proposed approach. The reported results show that the proposed solution approach is approximately six times faster and more space-efficient than the best existing method.

关键词： Temporal Network (Delta center dot gamma)-Clique enumeration algorithm D-Degeneracy Maximal Clique

来源：评论

学校读者我要写书评

暂无评论

Fine-Grained Complexity Analysis of Queries: From Decision to Counting and enumeration 20

Fine-Grained Complexity Analysis of Queries: From Decision t...

引用

39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)

作者： Durand, Arnaud Univ Paris Paris France

ISBN: (纸本)9781450371087

This paper is devoted to a complexity study of various tasks related to query answering such as deciding if a Boolean query is true or not, counting the size of the answer set or enumerating the results. It is a survey of some of the many tools from complexity measures trough algorithmic methods to conditional lower bounds that have been designed in the domain over the last years.

关键词： Query evaluation enumeration algorithm counting logic

来源：评论

学校读者我要写书评

暂无评论

A Two-Phase Approach for enumeration of Maximal (Δ, γ)-Cliques of a Temporal Network 32nd

A Two-Phase Approach for Enumeration of Maximal (Δ, γ)-Cli...

引用

32nd International Conference on Database and Expert Systems Applications (DEXA)

作者： Banerjee, Suman Pal, Bithika Indian Inst Technol Jammu India Indian Inst Technol Kharagpur W Bengal India

ISBN: (纸本)9783030864750;9783030864743

A Temporal Network is a graph whose topology is changing over time and represented as a collection of triplets of the form (u, v, t) that denotes the interaction between the agents u and v at time t. Analyzing and enumerating different structural patterns of such networks are important in different domains including social network analysis, computational biology, etc. In this paper, we study the problem of enumerating one such pattern: maximal (Delta, gamma)-Clique. Given a temporal network G(V, E, T), a Delta, gamma)-Clique is a vertex subset, time interval pair (chi, [t(a), t(b)]) such that between every pair of vertices of chi, there exist at least gamma links in each Delta duration in [t(a), t(b)]. The proposed methodology is broadly divided into two phases. In the first phase, each temporal link is processed for constructing (Delta, gamma)-Clique(s) with maximum duration. In the second phase, these initial cliques are expanded by vertex addition to form the maximal cliques. We show that the proposed methodology is correct, and running time, space requirement analysis has been done. From the experimentation on three real datasets, we observe that the proposed methodology enumerates all the maximal (Delta, gamma)-Cliques efficiently, particularly when the dataset is sparse. As a special case (gamma = 1), the proposed methodology is also able to enumerate (Delta, 1) equivalent to Delta-cliques with much less time compared to the existing methods.

关键词： Temporal Network (Delta, gamma)-Clique enumeration algorithm

来源：评论

学校读者我要写书评

暂无评论

Computing Bayes-Nash Equilibria through Support enumeration Methods in Bayesian Two-Player Strategic-Form Games

Computing Bayes-Nash Equilibria through Support Enumeration ...

引用

IEEE/WIC/ACM International Conferences on Web Intelligence (WI)/Intelligent Agent Technologies (IAT),

作者： Ceppi, Sofia Gatti, Nicola Basilico, Nicola Politecn Milan Dipartimento Elettron & Informat I-20133 Milan Italy

ISBN: (纸本)9781424453313

The computation of equilibria in games is a challenging task. The literature studies the problem of finding Nash equilibria with complete-information games in depth, but not enough attention is paid to searching for equilibria in Bayesian games. Customarily, these games are reduced to complete-information games and standard algorithms for computing Nash equilibria are employed. However, no work studied how these algorithms perform with Bayesian games. In this paper we focus on two-player strategic-form games. We show that the most efficient algorithm for computing Nash equilibria with GAMUT data (i.e., Porter-Nudelman-Shoham) is inefficient with Bayesian games, we provide an extension, and we experimentally evaluate its performance.

关键词： algorithmic game theory Bayes-Nash equilibrium enumeration algorithm

来源：评论

学校读者我要写书评

暂无评论

Enumerating floorplans with walls☆

引用

DISCRETE APPLIED MATHEMATICS 2024年 342卷 1-11页

作者： Yamanaka, Katsuhisa Nakano, Shin-ichi Iwate Prefectural Univ Morioka Japan Gunma Univ Maebashi Japan

Let P be a set of n points in the proper inside of an axis-aligned rectangle R, and each point in P has a type, which is h-type, v-type, or f-type. Those are shortened forms of horizontal type, vertical type, and free type. We wish to dissect R into a set S of n + 1 rectangles by n horizontal or vertical line segments so that each point in P is on the common boundary line segment between two rectangles in S, and also each h-type point in P is on a horizontal line segment, each v-type point in P is on a vertical line segment, and each f-type point in P is on a horizontal or vertical line segment. Such a dissection of R is called a feasible floorplan of R with respect to P. Each point in P corresponds to the location of a structurally necessary horizontal or vertical wall, or a column (pillar) to support the upper part. In this paper, when P consists of points of the three described types, we present an efficient algorithm that enumerates all the feasible floorplans of R with respect to P. The algorithm is based on the reverse search method and enumerates all the feasible floorplans in O(n |SP |) time using O(n2) space, after O(n log n) time preprocessing, where SP is the set of the feasible floorplans of R with respect to P. Moreover, we show that, after O(n log n) time preprocessing, one can enumerate all feasible floorplans in SP in O(n) delay using O(n2) space.(c) 2023 Elsevier B.V. All rights reserved.

关键词： algorithm enumeration enumeration algorithm Floorplan Feasible floorplan

来源：评论

学校读者我要写书评

暂无评论

Counting Convex and Non-Convex 4-Holes in a Point Set

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2021年第9期E104A卷 1094-1100页

作者： Sung, Young-Hun Bae, Sang Won Kyonggi Univ Div Comp Sci & Engn Suwon South Korea

In this paper, we present an algorithm that counts the number of empty quadrilaterals whose corners are chosen from a given set S of n points in general position. Our algorithm can separately count the number of convex or non-convex empty quadrilaterals in O(T) time, where T denotes the number of empty triangles in S. Note that T varies from Omega(n(2)) and O(n(3)) and the expected value of T is known to be Theta(n(2)) when the n points in S are chosen uniformly and independently at random from a convex and bounded body in the plane. We also show how to enumerate all convex and/or non-convex empty quadrilaterals in S in time proportional to the number of reported quadrilaterals, after O(T)-time preprocessing.

关键词： Erdos-Szekeres problem counting algorithm enumeration algorithm polygon discrete and computational geometry

来源：评论

学校读者我要写书评

暂无评论

Frontier-Based Search for Enumerating All Constrained Subgraphs with Compressed Representation

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2017年第9期E100A卷 1773-1784页

作者： Kawahara, Jun Inoue, Takeru Iwashita, Hiroaki Minato, Shin-ichi Nara Inst Sci & Technol Grad Sch Informat Sci Ikoma 6300192 Japan NTT Corp NTT Network Innovat Labs Yokosuka Kanagawa 2390847 Japan Fujitsu Labs Ltd Kawasaki Kanagawa 2118588 Japan Hokkaido Univ Grad Sch Informat Sci & Technol Sapporo Hokkaido 0600814 Japan

For subgraph enumeration problems, very efficient algorithms have been proposed whose time complexities are far smaller than the number of subgraphs. Although the number of subgraphs can exponentially increase with the input graph size, these algorithms exploit compressed representations to output and maintain enumerated subgraphs compactly so as to reduce the time and space complexities. However, they are designed for enumerating only some specific types of subgraphs, e.g., paths or trees. In this paper, we propose an algorithm framework, called the frontier-based search, which generalizes these specific algorithms without losing their efficiency. Our frontier-based search will be used to resolve various practical problems that include constrained subgraph enumeration.

关键词： zero-suppressed binary decision diagram froniter-based search enumeration algorithm subgraph

来源：评论

学校读者我要写书评

暂无评论

Enumerating connected induced subgraphs: Improved delay and experimental comparison

引用

DISCRETE APPLIED MATHEMATICS 2021年 303卷 262-282页

作者： Komusiewicz, Christian Sommer, Frank Philipps Univ Marburg Fachbereich Math & Informat Marburg Germany

We consider the problem of enumerating all connected induced subgraphs of order k in an undirected graph G = (V, E). Our main results are two enumeration algorithms with a delay of O(k(2)Delta) where Delta is the maximum degree in the input graph. This improves upon a previous delay bound (Elbassioni, 2015) for this problem. Moreover, we show that these two algorithms can be adapted to give algorithms for the problem of enumerating all connected induced subgraphs of order at most k with a delay of O(k + Delta). Finally, we perform an experimental comparison of several enumeration algorithms for k <= 10 and k >= vertical bar V vertical bar - 3. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Subgraph enumeration Polynomial Delay enumeration algorithm Reverse Search Degree-bounded Graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：