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

listing all delta partitions of a given set: algorithm design and results

OPEN COMPUTER SCIENCE 2024年第1期14卷

作者： Nofal, Samer German Jordanian Univ Dept Comp Sci Amman Jordan

Let alpha be a set ofnelements and delta be a nonnega-tive integer. A delta-partition of alpha is a set of pairwise disjointnonempty subsets of alpha such that the union of the subsets isequal to alpha and every subset has a size greater than *** an algorithm for computing all delta-partitions of agivenn-element set and show that the algorithm runs inn O(n)space and O(n)delaytime between any two succes-sive outputs of delta-partitions of the given set. An applicationof the notion of delta-partitions is illustrated in the followingscheduling problem. Suppose a factory hasnmachines and <= mnjobs to complete daily. Every job can be accom-plished by operating at least+delta 1machines. A machinecannot work on multiple jobs simultaneously. Accordingto a utilization policy of the factory's management, nomachine is allowed to be idle, so all machines should berunning on some job. Find a daily schedule of the factory'smachines satisfying all the mentioned constraints. Let alpha bethe set of the factory's machines. Then, an alpha's delta-partitionwithmsubsets is a legal schedule if every subset (in the delta-partition) includes exclusively+delta 1or more machinesthat run on the same job

关键词： constrained set partitions listing algorithm delay time

来源：评论

学校读者我要写书评

暂无评论

listing maximal k-relaxed-vertex connected components from large graphs

引用

INFORMATION SCIENCES 2023年 620卷 67-83页

作者： Hu, Shan Zhou, Yi Xiao, Mingyu Fu, Zhang-Hua Lu, Zhipeng Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 611731 Peoples R China Shenzhen Inst Artificial Intelligence & Robot Soc Chengdu Peoples R China Chinese Univ Hong Kong Shenzhen Peoples R China Huazhong Univ Sci & Technol Sch Comp Sci 1037 Luoyu Rd Wuhan 1037 Peoples R China

Cohesive group extraction is an important task in many applications such as graph visual-ization, system science, and bioinformatics. The k-vertex-connected component (k-VCC), which is a connected graph that remains connected whenever fewer than k vertices are removed, is a well-studied model for this task. However, the use of k-VCC model may cause resolution issues;thus, we use the k-relaxed-vertex connected component (k-RVCC) model, which effectively eliminates the problem. A k-RVCC is also a connected graph, but to disconnect it, at least n -k vertices must be removed, n is the vertex number of the graph. In this study, we investigate efficient practical algorithms for listing all maximal k-RVCCs from a given graph. Specifically, we first adapted the celebrate Bron-Kerbosch tree-search algorithm from listing cliques to listing k-RVCCs. We then design new branch-ing rules to reduce the number of branches and vertex-cut-based strategies to recursively partition the input graph into smaller independent pieces. Implementation techniques that accelerate the aforementioned algorithms were also investigated. Experiments on various large real networks validated the effectiveness of the proposed algorithms and demon-strated the efficiency of our algorithms in mining cohesive groups.(c) 2022 Elsevier Inc. All rights reserved.

关键词： Cohesive groups Graph theory k-relaxed-vertex connected component listing algorithm

来源：评论

学校读者我要写书评

暂无评论

ON THE DELAY TIME IN THE ENUMERATION OF ALL SIMPLE CYCLES OF A DIRECTED GRAPH

引用

Journal of Mathematical Sciences (United States) 2024年 1-6页

作者： Nofal, Samer Department of Computer Science German Jordanian University Amman Jordan

For the fundamental problem of enumeration of all simple cycles of a given directed graph with n vertices and m edges, it is known that the delay time between successive outputs of two simple cycles is O(n+m) where m∈O(n²). This paper shows that for a directed graph under a uniform probability distribution for the out-degrees of the vertices in the graph, all simple cycles of the graph can be listed with delay time O(nlnn) in expectation. © The Author(s), under exclusive licence to Springer Nature Switzerland AG 2024.

关键词： Directed graph Expected delay time listing algorithm Simple cycle

来源：评论

学校读者我要写书评

暂无评论

Computing and listing st-Paths in Public Transportation Networks

引用

THEORY OF COMPUTING SYSTEMS 2018年第3期62卷 600-621页

作者： Bohmova, Katerina Hafliger, Luca Mihalak, Matus Proger, Tobias Sacomoto, Gustavo Sagot, Marie-France Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland Maastricht Univ Dept Knowledge Engn Maastricht Netherlands INRIA Grenoble Rhone Alpes Montbonnot St Martin France Univ Lyon 1 UMR CNRS 5558 LBBE Lyon France

Given a set of directed paths (called lines) L, a public transportation network is a directed graph G (L) = (V (L) , A (L) ) which contains exactly the vertices and arcs of every line l a L. An st-route is a pair (pi, gamma) where gamma = aOE (c) l (1),aEuro broken vertical bar, l (h) > is a line sequence and pi is an st-path in G (L) which is the concatenation of subpaths of the lines l (1),aEuro broken vertical bar, l (h) , in this order. Given a threshold beta, we present an algorithm for listing all st-paths pi for which a route (pi, gamma) with |gamma| ae beta exists, and we show that the running time of this algorithm is polynomial with respect to the input and the output size. We also present an algorithm for listing all line sequences gamma with |gamma| ae beta for which a route (pi, gamma) exists, and show how to speed it up using preprocessing. Moreover, we show that for the problem of finding an st-route (pi, gamma) that minimizes the number of different lines in gamma, even computing an -approximation is NP-hard.

关键词： listing algorithm Public transportation NP-hardness

来源：评论

学校读者我要写书评

暂无评论

An algorithm for listing all Minimal Double Dominating Sets of a Tree

引用

FUNDAMENTA INFORMATICAE 2014年第4期130卷 415-421页

作者： Krzywkowski, Marcin Gdansk Univ Technol Fac Elect Telecommun & Informat Gdansk Poland Polish Acad Sci Inst Math PL-00901 Warsaw Poland

We provide an algorithm for listing all minimal double dominating sets of a tree of order n in time O(1.3248(n)). This implies that every tree has at most 1.3248(n) minimal double dominating sets. We also show that th... 详细信息

关键词： domination double domination minimal double dominating set tree combinatorial bound exact exponential algorithm listing algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimal Double Dominating Sets in Trees

Minimal Double Dominating Sets in Trees

引用

8th International Frontiers of algorithmics Workshop (FAW)

作者： Krzywkowski, Marcin Univ Johannesburg Dept Math Johannesburg South Africa

ISBN: (纸本)9783319080161;9783319080154

关键词： domination double domination minimal double dominating set tree combinatorial bound exact exponential algorithm listing algorithm

来源：评论

学校读者我要写书评

暂无评论

MINIMAL 2-DOMINATING SETS IN TREES

引用

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS 2013年第3期47卷 235-240页

作者： Krzywkowski, Marcin Gdansk Univ Technol Fac Elect Telecommun & Informat PL-80233 Gdansk Poland

We provide an algorithm for listing all minimal 2-dominating sets of a tree of order n in time O(1.3248(n)). This implies that every tree has at most 1.3248(n) minimal 2-dominating sets. We also show that this bound i... 详细信息

关键词： Domination 2-domination minimal 2-dominating set tree counting exact exponential algorithm listing algorithm

来源：评论

学校读者我要写书评

暂无评论

Trees having many minimal dominating sets

引用

INFORMATION PROCESSING LETTERS 2013年第8期113卷 276-279页

作者： Krzywkowski, Marcin Gdansk Univ Technol Fac Elect Telecommun & Informat PL-80233 Gdansk Poland

We disprove a conjecture by Skupien that every tree of order n has at most 2(n/2) minimal dominating sets. We construct a family of trees of both parities of the order for which the number of minimal dominating sets exceeds 1.416(n). We also provide an algorithm for listing all minimal dominating sets of a tree in time O(1.4656(n)). This implies that every tree has at most 1.4656(n) minimal dominating sets. (c) 2013 Elsevier B.V. All rights reserved.

关键词： Combinatorial problems Minimal dominating set Tree Combinatorial bound Exponential algorithm listing algorithm

来源：评论

学校读者我要写书评

暂无评论

Decomposition and enumeration of triangulated surfaces

引用

EXPERIMENTAL MATHEMATICS 2008年第2期17卷 153-166页

作者： Amendola, Gennaro Dept Math I-73100 Lecce Italy

We describe some theoretical results on triangulations of surfaces and we develop a theory on roots, decompositions, and genus surfaces. We apply this theory to describe an algorithm to list all triangulations of closed surfaces with at most a fixed number of vertices. We specialize-the theory to the case that the number of vertices is at most 11, and we obtain theoretical restrictions on genus surfaces, allowing us to obtain a list of all triangulations of closed surfaces with at most 11 vertices.

关键词： surface triangulation decomposition listing algorithm

来源：评论

学校读者我要写书评

暂无评论

listing all minimal separators of a graph

引用

SIAM JOURNAL ON COMPUTING 1998年第3期27卷 605-613页

作者： Kloks, T Kratsch, D Univ Twente Fac Appl Math NL-7500 AE Enschede Netherlands Univ Jena Fak Math & Informat D-07740 Jena Germany

An efficient algorithm listing all minimal vertex separators of an undirected graph is given. The algorithm needs polynomial time per separator that is found.

关键词： graph algorithm listing algorithm minimal separator good pair minimal pair

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：