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

Clustering as a dual problem to colouring

COMPUTATIONAL & APPLIED MATHEMATICS 2022年第4期41卷 1-36页

作者： Ikica, Barbara Gabrovsek, Bostjan Povh, Janez Zerovnik, Janez Univ Ljubljana Fac Math & Phys Ljubljana Slovenia Inst Math Phys & Mech Ljubljana Slovenia Univ Ljubljana Fac Mech Engn Ljubljana Slovenia

An essential step towards gaining a deeper insight into intricate mechanisms underlying the formation and functioning of complex networks is extracting and understanding their building blocks encoded in the clustering structure. At its core, the problem of partitioning vertices into clusters may be regarded as a dual problem to vertex colouring and, as such, permitted us to leverage the Petford-Welsh colouring algorithm to devise a highly scalable decentralised heuristic approach to cluster detection. As long as the graph under scrutiny admits a fairly well-defined clustering structure per se, the modified Petford-Welsh algorithm tends to perform on a par with or even surpasses existing techniques.

关键词： graph algorithm Community detection The Petford-Welsh algorithm Simulated annealing Complex networks

来源：评论

学校读者我要写书评

暂无评论

Reconfiguring (non-spanning) arborescences

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期943卷 131-141页

作者： Ito, Takehiro Iwamasa, Yuni Kobayashi, Yasuaki Nakahata, Yu Otachi, Yota Wasa, Kunihiro Tohoku Univ Grad Sch Informat Sci Sendai Japan Kyoto Univ Grad Sch Informat Kyoto Japan Hokkaido Univ Grad Sch Informat Sci & Technol Sapporo Japan Nara Inst Sci & Technol Div Informat Sci Nara Japan Nagoya Univ Grad Sch Informat Nagoya Japan Hosei Univ Fac Sci & Engn Tokyo Japan

In this paper, we investigate the computational complexity of subgraph reconfiguration problems in directed graphs. More specifically, we focus on the problem of reconfiguring arborescences in a digraph, where an arborescence is a directed graph such that its underlying undirected graph forms a tree and all vertices have in-degree at most 1. Given two arborescences in a digraph, the goal of the problem is to determine whether there is a (reconfiguration) sequence of arborescences between the given arborescences such that each arborescence in the sequence can be obtained from the previous one by removing an arc and then adding another arc. We show that this problem can be solved in polynomial time, whereas the problem is PSPACE-complete when we restrict arborescences in a reconfiguration sequence to directed paths or relax to directed acyclic graphs. We also show that there is a polynomial-time algorithm for finding a shortest reconfiguration sequence between two spanning arborescences. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Combinatorial reconfiguration graph algorithm

来源：评论

学校读者我要写书评

暂无评论

I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs

引用

THEORETICAL COMPUTER SCIENCE 2015年第1期575卷 33-41页

作者： Bhushan, Alka Sajith, G. Indian Inst Technol Guwahati Dept Comp Sci & Engn Gauhati 781039 Assam India

The problem of finding the minimum cut of an undirected unweighted graph is studied on the external memory model. First, a lower bound of Omega((E/V)Sort(V)) on the number of I/Os is shown for the problem, where V is the number of vertices and E is the number of edges. Then the following are presented, (1) a deterministic minimum cut algorithm that uses O(min{c(7) (log(3+is an element of) E)(MST(V, E)), c(log E)(MST(V, E)) + (V /root M) Sort(V)}) I/Os;here is an element of > 0 is a small constant, MST(V, E) is the number of I/Os needed to compute a minimum spanning tree of the graph, and c is the value of the minimum cut. The algorithm performs better on dense graphs than the algorithm of [1], which requires O(E + c(2)V log(V/c)) I/Os, when executed on the external memory model. For a delta-fat graph (for delta > 0, the maximum tree packing of the graph is at least (I + delta)c/2), our algorithm computes a minimum cut in O(c(log E)MST(V, E)) I/Os. (2) A randomized algorithm that computes minimum cut with high probability in O(c(log E).MST(V, E) Sort(E) log(2) V + V/B Sort(V) log V) I/Os. (3) A (2 + is an element of)-minimum cut algorithm that requires O((E/V) MST(V, E)) I/Os. (C) 2014 Elsevier B.V. All rights reserved.

关键词： graph algorithm External memory algorithm I/O complexity Minimum cut Lower bound

来源：评论

学校读者我要写书评

暂无评论

An evaluation of reordering algorithms to reduce the computational cost of the incomplete Cholesky-conjugate gradient method

引用

COMPUTATIONAL & APPLIED MATHEMATICS 2018年第3期37卷 2965-3004页

作者： Gonzaga de Oliveira, Sanderson L. Bernardes, J. A. B. Chagas, G. O. Univ Fed Lavras Lavras Brazil

This paper is concerned with applying bandwidth and profile reduction reordering algorithms prior to computing an incomplete Cholesky factorization and using this as a preconditioner for the conjugate gradient method. Hundreds of reordering algorithms have been proposed to solve the problems of bandwidth and profile reductions since the mid-1960s. In previous publications, a large range of heuristics for bandwidth and/or profile reductions was reviewed. Based on this experience, 13 heuristics were selected as the most promising methods. These are evaluated in this paper along with a variant of the breadth-first search procedure that is proposed. Numerical results confirm the effectiveness of this modified reordering algorithm for linear systems derived from specific application areas. Moreover, the most promising heuristics for several application areas are identified when reducing the computational cost of the incomplete Cholesky-conjugate gradient method.

关键词： Bandwidth reduction Profile reduction Combinatorial optimization Heuristics Metaheuristics Reordering algorithms Sparse matrices Renumbering Ordering graph labeling Conjugate gradient method graph algorithm Sparse symmetric positive-definite linear systems Incomplete Cholesky factorization

来源：评论

学校读者我要写书评

暂无评论

Efficient semi-external depth-first search

引用

INFORMATION SCIENCES 2022年 599卷 170-191页

作者： Wan, Xiaolong Wang, Hongzhi Harbin Inst Technol Sch Comp Sci & Technol Harbin Peoples R China

As graphs grow in size, many real-world graphs are difficult to load into the primary memory of a computer. Thus, computing depth-first search (DFS) results (i.e., depth-first order or DFS-Tree) on the semi-external memory model is important to investigate. Semi external algorithms assume that the primary memory can at least hold a spanning tree T of a graph G and gradually restructure T into a DFS-Tree, which is nontrivial. In this paper, we present a comprehensive study for the semi-external DFS problem. Based on a theoretical analysis of this problem, we introduce a new semi-external DFS algorithm called EPDFS with a lightweight index N thorn -index. Unlike traditional algorithms, we focus on addressing such a complex problem efficiently with fewer I/Os, simpler CPU calculations (implementation-friendly), and less random I/O accesses (key-to-efficiency). Extensive experimental evaluations are performed on both synthetic and real graphs, and experimental results confirm that the proposed EP-DFS algorithm markedly outperforms existing algorithms. (c) 2022 Elsevier Inc. All rights reserved.

关键词： Depth-first search Semi-external memory graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Complexity and algorithms for Semipaired Domination in graphs

引用

THEORY OF COMPUTING SYSTEMS 2020年第7期64卷 1225-1241页

作者： Henning, Michael A. Pandey, Arti Tripathi, Vikash Univ Johannesburg Dept Math & Appl Math ZA-2006 Auckland Pk South Africa Indian Inst Technol Ropar Dept Math Nangal Rd Rupnagar 140001 Punjab India

For a graph G = (V, E) with no isolated vertices, a set D subset of V is called a semipaired dominating set of G if (i) D is a dominating set of G, and (ii) D can be partitioned into two element subsets such that the vertices in each two element set are at distance at most two. The minimum cardinality of a semipaired dominating set of G is called the semipaired domination number of G, and is denoted by gamma(pr2)(G). TheMINIMUM SEMIPAIRED DOMINATION problem is to find a semipaired dominating set of G of cardinality gamma(pr2)(G). In this paper, we initiate the algorithmic study of the MINIMUM SEMIPAIRED DOMINATION problem. We show that the decision version of the MINIMUM SEMIPAIRED DOMINATION problem is NP-complete for bipartite graphs and chordal graphs. On the positive side, we present a linear-time algorithm to compute a minimum cardinality semipaired dominating set of interval graphs. We also propose a 1 + ln(2 Delta + 2)-approximation algorithm for the MINIMUM SEMIPAIRED DOMINATION problem, where Delta denotes the maximum degree of the graph and show that the MINIMUM SEMIPAIRED DOMINATION problem cannot be approximated within (1 - epsilon) ln vertical bar V vertical bar for any epsilon > 0 unless P=NP.

关键词： Domination Semipaired domination Interval graphs graph algorithm NP-complete Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

algorithms and obstructions for linear-width and related search parameters

引用

DISCRETE APPLIED MATHEMATICS 2000年第1-3期105卷 239-271页

作者： Thilikos, DM Univ Politecn Catalunya Dept Llenguatges & Sistemes Informat E-08034 Barcelona Spain

The linear-width of a graph G is defined to be the smallest integer k such that the edges of G can be arranged in a linear ordering (e(1),...,e(r)) in such a way that for every i = 1,..., r - 1, there are at most k vertices incident to edges that belong both to {e(1),...,e(i)} and to {e(i+1),...,e(r)}. In this paper, we give a set of 57 graphs and prove that it is the set of the minimal forbidden miners for the class of graphs with linear-width at most two. Our proof also gives a linear time algorithm that either reports that a given graph has linear-width more than two or outputs an edge ordering of minimum linear-width. We further prove a structural connection between linear-width and the mixed search number which enables us to determine, for any k greater than or equal to 1, the set of acyclic forbidden miners for the class of graphs with linear-width less than or equal to k. Moreover, due to this connection, our algorithm can be transfered to two linear time algorithms that check whether a graph has mixed search or edge search number at most two and, if so, construct the corresponding sequences of search moves. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： graph algorithm linear width graph minor obstruction set graph searching

来源：评论

学校读者我要写书评

暂无评论

Safety in s-t Paths, Trails and Walks

引用

algorithmICA 2022年第3期84卷 719-741页

作者： Cairo, Massimo Khan, Shahbaz Rizzi, Romeo Schmidt, Sebastian Tomescu, Alexandru, I Univ Helsinki Dept Comp Sci Helsinki Finland Univ Verona Dept Comp Sci Verona Italy

Given a directed graph G and a pair of nodes s and t, an s-t bridge of G is an edge whose removal breaks all s-t paths of G (and thus appears in all s-t paths). Computing all s-t bridges of G is a basic graph problem, solvable in linear time. In this paper, we consider a natural generalisation of this problem, with the notion of "safety" from bioinformatics. We say that a walk W is safe with respect to a set W of s-t walks, if W is a subwalk of all walks in W. We start by considering the maximal safe walks when W consists of: all s-t paths, all s-t trails, or all s-t walks of G. We show that the solutions for the first two problems immediately follow from finding all s-t bridges after incorporating simple characterisations. However, solving the third problem requires non-trivial techniques for incorporating its characterisation. In particular, we show that there exists a compact representation computable in linear time, that allows outputting all maximal safe walks in time linear in their length. Our solutions also directly extend to multigraphs, except for the second problem, which requires a more involved approach. We further generalise these problems, by assuming that safety is defined only with respect to a subset of visible edges. Here we prove a dichotomy between the s-t paths and s-t trails cases, and the s-t walks case: the former two are NP-hard, while the latter is solvable with the same complexity as when all edges are visible. We also show that the same complexity results hold for the analogous generalisations of s-t articulation points (nodes appearing in all s-t paths). We thus obtain the best possible results for natural "safety"-generalisations of these two fundamental graph problems. Moreover, our algorithms are simple and do not employ any complex data structures, making them ideal for use in practice.

关键词： Directed graph Connectivity problem graph algorithm Strong bridge Strong articulation point Safety Genome assembly

来源：评论

学校读者我要写书评

暂无评论

Computing bounded-degree phylogenetic roots of disconnected graphs

引用

JOURNAL OF algorithmS-COGNITION INFORMATICS AND LOGIC 2006年第2期59卷 125-148页

作者： Chen, Zhi-Zhong Tsukiji, Tatsuie Tokyo Denki Univ Dept Math Sci Hatoyama Saitama 3500394 Japan Tokyo Denki Univ Dept Informat Sci Hatoyama Saitama 3500394 Japan

The Phylogenetic kth Root Problem (PRk) is the problem of finding a (phylogenetic) tree T from a given graph G = (V, E) such that (1) T has no degree-2 internal nodes, (2) the external nodes (i.e., leaves) of T are exactly the elements of V, and (3) (u, v) is an element of E if and only if the distance between it and v in tree T is at most k, where k is some fixed threshold k. Such a tree T, if exists. is called a phylogenetic kth root of graph G. The computational complexity of PRk is open, except for k <= 4. Recently, Chen et al. investigated PRk under a natural restriction that the maximum degree of the phylogenetic root is bounded from above by a constant. They presented a linear-time algorithm that determines if a given connected G has such a phylogenetic kth root, and if so. demonstrates one. In this paper, we supplement their work by presenting a linear-time algorithm for disconnected graphs. (c) 2005 Elsevier Inc. All rights reserved.

关键词： phylogeny phylogenetic root computational biology graph power tree power graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Robustness of First- and Second-Order Consensus algorithms for a Noisy Scale-Free Small-World Koch Network

引用

IEEE TRANSACTIONS ON CONTROL SYSTEMS TECHNOLOGY 2017年第1期25卷 342-350页

作者： Yi, Yuhao Zhang, Zhongzhi Shan, Liren Chen, Guanrong Fudan Univ Sch Comp Sci Shanghai Key Lab Intelligent Informat Proc Shanghai 200433 Peoples R China City Univ Hong Kong Dept Elect Engn Hong Kong Hong Kong Peoples R China

In this brief, we study first- and second-order consensus algorithms for the scale-free small-world Koch network, where vertices are subject to white noise. We focus on three cases of consensus schemes: 1) first-order leaderless algorithm;2) first-order algorithm with a single leader;and 3) second-order leaderless algorithm. We are concerned with the coherence of the Koch network in the H-2 norm, which captures the level of agreement of vertices in face of stochastic disturbances. Based on the particular network construction, we derive explicit expressions of the coherence for all the three consensus algorithms, as well as their dependence on the network size. Particularly, for the first-order leader-follower model, we show that coherence relies on the shortest-path distance between the leader and the largest-degree vertices, as well as the degree of the leader. The asymptotic behaviors for coherence of the three consensus algorithms in Koch network behave differently from those associated with other networks lacking scale-free small-world features, indicating significant influences of the scale-free small-world topology on the performance of the consensus algorithms in noisy environments.

关键词： Distributed average consensus graph algorithm noise scale-free network small-world network

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：