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

AN algorithm FOR THE enumeration OF SPANNING-TREES

BIT 1986年第1期26卷 44-62页

作者： WINTER, P UNIV COPENHAGEN INST DATALDIKUDK-2200 COPENHAGEN NDENMARK

enumeration of spanning trees of an undirected graph is one of the graph problems that has received much attention in the literature. In this paper a new enumeration algorithm based on the idea of contractions of the graph is presented. The worst-case time complexity of the algorithm isO(n+m+nt) wheren is the number of vertices,m the number of edges, andt the number of spanning trees in the graph. The worst-case space complexity of the algorithm isO(n ²). Computational analysis indicates that the algorithm requires less computation time than any other of the previously best-known algorithms.

关键词： Graph Theory Spanning Tree enumeration algorithm

来源：评论

学校读者我要写书评

暂无评论

Extension of backward induction for the enumeration of pure Nash equilibria outcomes

引用

Operations Research Letters 2025年 61卷

作者： Zappalà, Paolo Benhamiche, Amal Chardy, Matthieu De Pellegrini, Francesco Figueiredo, Rosa Orange Innovation Orange 44 Avenue de la République Châtillon 92320 France LIA Avignon Université 339 Chem. des Meinajaries Avignon 84000 France

Extensive-form games with perfect information admit at least one Nash equilibrium. The backward induction algorithm identifies in linear time a Nash equilibrium of the game, called subgame perfect. We introduce an extension of the backward induction algorithm which is the first to identify all the outcomes of pure Nash equilibria of the game in linear time with respect to the size of the game. © 2025 Elsevier B.V.

关键词： Backward induction enumeration algorithm Extensive-form games Nash equilibria

来源：评论

学校读者我要写书评

暂无评论

Improved Lattice enumeration algorithms by Primal and Dual Reordering Methods 24th

Improved Lattice Enumeration Algorithms by Primal and Dual R...

引用

24th International Conference on Information Security and Cryptology (ICISC)

作者： Yamamura, Kazuki Wang, Yuntao Fujisaki, Eiichiro NTT Social Informat Labs Tokyo Japan Osaka Univ Grad Sch Engn Osaka Japan Japan Adv Inst Sci & Technol Sch Informat Sci Nomi Japan

ISBN: (纸本)9783031088964;9783031088957

The security of lattice-based cryptosystems is generally based on the hardness of the Shortest Vector Problem (SVP). There are two common categories of lattice algorithms to solve SVP: search algorithms and reduction algorithms. The original enumeration algorithm (ENUM) is one of the former algorithms which run in exponential time due to the exhaustive search. Further, ENUM is used as a subroutine for the BKZ algorithm, which is one of the most practical reduction algorithms. It is a critical issue to reduce the computational complexity of ENUM. In this paper, first, we improve the mechanism in the so-called reordering method proposed by Wang in ACISP 2018. We call this improvement Primal Projective Reordering (PPR) method which permutates the projected vectors by decreasing norms;therefore it performs better to reduce the number of search nodes in ENUM. Then, we propose a Dual Projective Reordering (DPR) method permutating the projected vectors in its dual lattice. In addition, we propose a condition to decide whether the reordering method should be adopted or not. Preliminary experimental results show that our proposed reordering methods can successfully reduce the number of ENUM search nodes comparing to the predecessor, e.g., PPR reduces around 9.6% on average in 30-dimensional random lattices, and DPR reduces around 32.8% on average in 45-dimensional random lattices. Moreover, our simulation shows that the higher the lattice dimension, the more the proposed reordering method can reduce ENUM search nodes.

关键词： Lattice cryptography enumeration algorithm Reordering method Dual lattice

来源：评论

学校读者我要写书评

暂无评论

Linear amortized time enumeration algorithms for compatible Euler trails in edge-colored graphs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2023年第2期45卷 73-73页

作者： Bai, Yuhang Guo, Zhiwei Zhang, Shenggui Bai, Yandong Northwestern Polytech Univ Sch Math & Stat Xian 710129 Shaanxi Peoples R China Northwestern Polytech Univ Xian Budapest Joint Res Ctr Combinator Xian 710129 Shaanxi Peoples R China Yanan Univ Sch Math & Comp Sci Yanan 716000 Shaanxi Peoples R China

A compatible Euler trail (tour) in an edge-colored graph is an Euler trail (tour) in which each two edges traversed consecutively along the Euler trail (tour) have distinct colors. In this paper, we show that the problem of counting compatible Euler trails in edge-colored graphs is #P-complete, and develop O(m N) time algorithms for enumerating compatible Euler trails (tours) in edge-colored graphs with m edges and N compatible Euler trails (tours). It is worth mentioning that our algorithms can run in O(N) time when there is no vertex v with degree 4 and maximum monochromatic degree 2.

关键词： Edge-colored graph Compatible Euler trail enumeration algorithm Linear amortized time

来源：评论

学校读者我要写书评

暂无评论

enumeration of all wedged equilibrium configurations in contact problem with Coulomb friction

引用

COMPUTER METHODS IN APPLIED MECHANICS AND ENGINEERING 2010年第17-20期199卷 1202-1215页

作者： Fujita, Ryo Kanno, Yoshihiro Univ Tokyo Dept Math Informat Grad Sch Informat Sci & Technol Bunkyo Ku Tokyo 1138656 Japan

For a linear structure subjected to the unilateral contact condition with a fixed obstacle, we refer to a non-trivial equilibrium state as a wedged configuration. Finding a wedged configuration is called a wedging problem. This paper discusses theoretical properties of solution set of the finite-dimensional wedging problem with the Coulomb friction, and presents numerical methods for computing all the wedged configurations. We propose algorithms for enumerating all the finitely many representative solutions, with which we can completely describe the solution set of the wedging problem. There exists a positive critical friction coefficient defined as the minimum value of friction coefficient with which at least one wedged configuration exists. We also propose an algorithm for computing the critical friction coefficient, which is based on the bisection method and the second-order cone program. (c) 2009 Elsevier B.V. All rights reserved.

关键词： Coulomb friction Complementarity problem enumeration algorithm Double description method Second-order cone program

来源：评论

学校读者我要写书评

暂无评论

Efficient enumeration of all ladder lotteries and its application

引用

THEORETICAL COMPUTER SCIENCE 2010年第16-18期411卷 1714-1722页

作者： Yamanaka, Katsuhisa Nakano, Shin-ichi Matsui, Yasuko Uehara, Ryuhei Nakada, Kento Univ Electrocommun Grad Sch Informat Syst Tokyo 1828585 Japan Gunma Univ Dept Comp Sci Gunma 3768515 Japan Tokai Univ Dept Math Sci Kanagawa 2591292 Japan Japan Adv Inst Sci & Technol Sch Informat Sci Nomi Ishikawa 9231292 Japan Wakkanai Hokusei Gakuen Univ Fac Integrated Media Wakkanai Hokkaido 0970013 Japan

A ladder lottery, known as "Amidakuji" in Japan, is a common way to choose a permutation randomly. A ladder lottery L corresponding to a given permutation pi is optimal if L has the minimum number of horizontal lines among the ladder lotteries corresponding to pi. In this paper we show that for any two optimal ladder lotteries L-1 and L-2 of a permutation, there exists a sequence of local modifications which transforms L-1 into L-2. We also give an algorithm to enumerate all optimal ladder lotteries of a given permutation. By setting pi = (n, n - 1,..., 1), the algorithm enumerates all arrangements of n pseudolines efficiently. By implementing the algorithm we compute the number of arrangements of n pseudolines for each n <= 11. (C) 2010 Elsevier B.V. All rights reserved.

关键词： enumeration algorithm Family tree Ladder lottery Pseudoline arrangement

来源：评论

学校读者我要写书评

暂无评论

Efficient enumeration of dominating sets for sparse graphs

引用

DISCRETE APPLIED MATHEMATICS 2021年 303卷 283-295页

作者： Kurita, Kazuhiro Wasa, Kunihiro Arimura, Hiroki Uno, Takeaki Hokkaido Univ IST Sapporo Hokkaido Japan Natl Inst Informat Tokyo Japan Toyohashi Univ Technol Toyohashi Aichi Japan

A dominating set D of a graph G is a set of vertices such that any vertex in G is in D or its neighbor is in D. enumeration of minimal dominating sets in a graph is one of the central problems in enumeration study since enumeration of minimal dominating sets corresponds to the enumeration of minimal hypergraph transversals. The output-polynomial time enumeration of minimal hypergraph transversals is an interesting open problem. On the other hand, enumeration of dominating sets including non-minimal ones has not been received much attention. In this paper, we address enumeration problems for dominating sets from sparse graphs which are degenerate graphs and graphs with large girth, and we propose two algorithms for solving the problems. The first algorithm enumerates all the dominating sets for a k-degenerate graph in O (k) time per solution using O (n + m) space, where n and m are respectively the number of vertices and edges in an input graph. That is, the algorithm is optimal for graphs with constant degeneracy such as trees, planar graphs, H-minor free graphs with some fixed H. The second algorithm enumerates all the dominating sets in constant time per solution for input graphs with girth at least nine. (C) 2021 Elsevier B.V. All rights reserved.

关键词： enumeration algorithm Polynomial amortized time Dominating set Girth Degeneracy

来源：评论

学校读者我要写书评

暂无评论

Constant Time enumeration of Subtrees with Exactly k Nodes in a Tree

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2014年第3期E97D卷 421-430页

作者： Wasa, Kunihiro Kaneta, Yusaku Uno, Takeaki Arimura, Hiroki Hokkaido Univ Grad Sch Informat Sci & Technol Sapporo Hokkaido 0600814 Japan Natl Inst Informat Tokyo 1018430 Japan

By the motivation to discover patterns in massive structured data in the form of graphs and trees, we study a special case of the k-subtree enumeration problem with a tree of n nodes as an input graph, which is originally introduced by (Ferreira, Grossi, and Rizzi, ESA' 11, 275-286, 2011) for general graphs. Based on reverse search technique (Avis and Fukuda, Discrete Appl. Math., vol.65, pp.21-46, 1996), we present the first constant delay enumeration algorithm that lists all k-subtrees of an input rooted tree in O(1) worst-case time per subtree. This result improves on the straightforward application of Ferreira et al's algorithm with O(k) amortized time per subtree when an input is restricted to tree. Finally, we discuss an application of our algorithm to a modification of the graph motif problem for trees.

关键词： graph algorithm enumeration algorithm constant delay enumeration motif discovery tree mining

来源：评论

学校读者我要写书评

暂无评论

Efficient enumeration of Induced Matchings in a Graph without Cycles with Length Four

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2018年第9期E101A卷 1383-1391页

作者： Kurita, Kazuhiro Wasa, Kunihiro Uno, Takeaki Arimura, Hiroki Hokkaido Univ IST Sapporo Hokkaido 0600814 Japan Natl Inst Informat Tokyo 1018430 Japan

In this study, we address a problem pertaining to the induced matching enumeration. An edge set M is an induced matching of a graph G = (V;E). The enumeration of matchings has been widely studied in literature;however, there few studies on induced matching. A straightforward algorithm takes O(Delta(2)) time for each solution that is coming from the time to generate a subproblem, where Delta is the maximum degree in an input graph. To generate a subproblem, an algorithm picks up an edge e and generates two graphs, the one is obtained by removing e from G, the other is obtained by removing e, adjacent edge to e, and edges adjacent to adjacent edge of e. Since this operation needs O (Delta(2)) time, a straightforward algorithm enumerates all induced matchings in O (Delta(2)) time per solution. We investigated local structures that enable us to generate subproblems within a short time and proved that the time complexity will be O (1) if the input graph is C-4-free. A graph is C-4-free if and only if none of its subgraphs have a cycle of length four.

关键词： enumeration algorithm induced subgraph induced matching constant amortized time enumeration

来源：评论

学校读者我要写书评

暂无评论

Constant amortized time enumeration of Eulerian trails

引用

THEORETICAL COMPUTER SCIENCE 2022年 923卷 1-12页

作者： Kurita, Kazuhiro Wasa, Kunihiro Natl Inst Informat Tokyo Japan Toyohashi Univ Technol Toyohashi Aichi Japan Hosei Univ Tokyo Japan

In this paper, we consider enumeration problems for edge-distinct and vertex-distinct Eulerian trails. Two Eulerian trails are said to be edge-distinctif the edge sequences are not identical, and they are said to be vertex-distinctif the vertex sequences are not identical. To solve these problems, we propose optimal enumeration algorithms that run in O(N+ m) total time, where Nis the number of solutions and mis the number of edges in an input connected graph. The proposed algorithms are based on the reverse search technique introduced by [Avis and Fukuda, DAM 1996], and the push-out amortization technique introduced by [Uno, WADS 2015]. (c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Eulerian trail enumeration algorithm Output-sensitive algorithm Constant amortized time

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：