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

Sharp threshold for embedding balanced spanning trees in random geometric graphs

JOURNAL OF GRAPH THEORY 2024年第1期107卷 107-125页

作者： Diaz, Alberto Espuny Lichev, Lyuben Mitsche, Dieter Wesolek, Alexandra Tech Univ Ilmenau Inst Math Ilmenau Germany Univ Jean Monnet Inst Camille Jordan St Etienne France Pont Univ Catolica IMC Santiago Chile Simon Fraser Univ Dept Math Burnaby BC Canada

A rooted tree is balanced if the degree of a vertex depends only on its distance to the root. In this paper we determine the sharp threshold for the appearance of a large family of balanced spanning trees in the random geometric graph G(n,r,d) ${\mathscr{G}}(n,r,d)$. In particular, we find the sharp threshold for balanced binary trees. More generally, we show that all sequences of balanced trees with uniformly bounded degrees and height tending to infinity appear above a sharp threshold, and none of these appears below the same value. Our results hold more generally for geometric graphs satisfying a mild condition on the distribution of their vertex set, and we provide a polynomial time algorithm to find such trees.

关键词： linear-time algorithm random geometric graphs sharp threshold spanning trees

来源：评论

学校读者我要写书评

暂无评论

Computation of Grundy dominating sequences in (co-)bipartite graphs

引用

COMPUTATIONAL & APPLIED MATHEMATICS 2023年第8期42卷 1-17页

作者： Bresar, Bostjan Pandey, Arti Sharma, Gopika Univ Maribor Fac Nat Sci & Math Maribor Slovenia Inst Math Phys & Mech Ljubljana Slovenia Indian Inst Technol Ropar Dept Math Rupnagar India

A sequence S of vertices of a graph G is called a dominating sequence of G if (1) each vertex v of S dominates a vertex of G that was not dominated by any of the vertices preceding vertex v in S, and (2) every vertex of G is dominated by at least one vertex of S. The Grundy Domination problem is to find a longest dominating sequence for a given graph G. It has been known that the decision version of the Grundy Domination problem is NP-complete even when restricted to chordal graphs. In this paper, we prove that the decision version of the Grundy Domination problem is NP-complete for bipartite graphs and co-bipartite graphs. On the positive side, we present a linear-time algorithm that solves the Grundy Domination problem for chain graphs, which form a subclass of bipartite graphs.

关键词： Dominating sequence Bipartite graph Chain graphs Computational complexity linear-time algorithm

来源：评论

学校读者我要写书评

暂无评论

ORIENTATION OF FITCH GRAPHS AND RECONCILIATION-FREE INFERENCE OF HORIZONTAL GENE TRANSFER IN GENE TREES

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2023年第3期37卷 2172-2207页

作者： Schaller, David Hellmuth, Marc Stadler, Peter F. Univ Leipzig Dept Comp Sci Bioinformat Grp D-04107 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinformat D-04107 Leipzig Germany Stockholm Univ Dept Math Fac Sci SE-10691 Stockholm Sweden Univ Leipzig German Ctr Integrat Biodivers Res iDiv Halle Jena Competence Ctr Scalable Data Serv & Solut Dresden Leipzig Res Ctr Civilizat Dis D-04103 Leipzig Germany Univ Leipzig Univ Leipzig Ctr Biotechnol & Biomed Max Planck Inst Math Sci D-04103 Leipzig Germany Univ Vienna Inst Theoret Chem A-1090 Vienna Austria Univ Nacl Colombia Fac Ciencias Bogota Colombia Santa Fe Inst Santa Fe NM 87501 USA

Horizontal gene transfer (HGT) events partition a gene tree T, and thus its leaf set X, into subsets of genes whose evolutionary history is described by speciation and duplication events alone. Two genes thus are xenologs if and only if they belong to two different sets of this partition P. Indirect phylogenetic methods can be used to infer the partition P of X from sequence similarity or evolutionary distances without any a priori knowledge about the underlying tree T. In this contribution, we assume that a partition P of the gene set X and a usually incompletely resolved estimate T of the original gene tree on X are known. We then ask to what extent T and P can be combined to determine the horizontal transfer edges in T and thus the orientation of the HGT events that separate the sets of P. If T and P are compatible, it can be decided for each pair of genes x and y whether there always exists or never exists a horizontal gene transfer in T along the path connecting y and the most recent common ancestor of x and y, and thus a directed edge (x, y) in the so-called Fitch graph of the gene family. We generalize this result to insufficiently resolved gene trees. We show that the classification of a gene pair (x, y) can be computed in constant time after linear-time preprocessing. Using simulated gene family histories, we observe empirically that the vast majority of horizontal transfer edges in the gene tree T can be recovered unambiguously from the knowledge of the partition P. All algorithms developed here are implemented and freely available within the Python package AsymmeTree hosted at https://***/david-schaller/AsymmeTree.

关键词： gene families xenology horizontal gene transfer Fitch graph partition linear-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Explicit formulas for the inverses of Toeplitz matrices, with applications

引用

PROBABILITY THEORY AND RELATED FIELDS 2023年第1-2期185卷 513-552页

作者： Inoue, Akihiko Hiroshima Univ Dept Math Higashihiroshima 7398526 Japan

We derive novel explicit formulas for the inverses of truncated block Toeplitz matrices that correspond to a multivariate minimal stationary process. The main ingredients of the formulas are the Fourier coefficients of the phase function attached to the spectral density of the process. The derivation of the formulas is based on a recently developed finite prediction theory applied to the dual process of the stationary process. We illustrate the usefulness of the formulas by two applications. The first one is a strong convergence result for solutions of general block Toeplitz systems for a multivariate short-memory process. The second application is closed-form formulas for the inverses of truncated block Toeplitz matrices corresponding to a multivariate ARMA process. The significance of the latter is that they provide us with a linear-time algorithm to compute the solutions of corresponding block Toeplitz systems.

关键词： Toeplitz matrix Finite prediction Dual process Toeplitz system linear-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Strong transitivity of a graph

引用

DISCRETE MATHEMATICS algorithmS AND APPLICATIONS 2025年第4期17卷

作者： Paul, Subhabrata Santra, Kamal Indian Inst Technol Patna Dept Math Patna 801106 Bihar India

A vertex partition pi = {V-1,V-2,& mldr;,V-k} of G is called a transitive partition of size k if V-i dominates V-j for all 1 = degG(y). A vertex partition pi = {V-1,V-2,& mldr;,V-k} of G is called a strong tra... 详细信息

A vertex partition pi = {V-1,V-2,& mldr;,V-k} of G is called a transitive partition of size k if V-i dominates V-j for all 1 <= i < j <= k. For two disjoint subsets A and B of V, we say A strongly dominates B if for every vertex y is an element of B, there exists a vertex x is an element of A, such that xy is an element of E and degG(x) >= degG(y). A vertex partition pi = {V-1,V-2,& mldr;,V-k} of G is called a strong transitive partition of size k if V-i strongly dominates Vj for all 1 <= i < j <= k. The maximum strong transitivity problem involves finding a strong transitive partition of a given graph with the maximum number of parts. In this paper, we initiate the study of this variation of transitive partition from an algorithmic point of view. We show that the decision version of this problem is NP-complete for chordal graphs. On the positive side, we prove that this problem can be solved in linear time for trees and split graphs.

关键词： Strong transitivity NP-completeness linear-time algorithm trees split graphs chordal graphs

来源：评论

学校读者我要写书评

暂无评论

algorithmic results in secure total dominating sets on graphs

引用

THEORETICAL COMPUTER SCIENCE 2022年 918卷 1-17页

作者： Poureidi, Abolfazl Shahrood Univ Technol Fac Math Sci Shahrood Iran

Given a graph G = (V, E), a (total) dominating set of G is a subset D & SUBE;V such that each vertex in V \ D (respectively, V ) is adjacent to at least one vertex in D. A (total) dominating set D of G is a secure (total) dominating set if for each v & ISIN;V \ D there is a vertex u & ISIN;D adjacent to v such that (D \ {u}) & OR;{v} is also a (total) dominating set of G. The minimum cardinality of a secure (total) dominating set of G is called the secure (total) domination number of G. The secure (total) domination problem is to find a minimum secure (total) dominating set of any graph. In this paper, we study the secure total domination problem. We show that the problem restricted to trees is solvable in linear-time, the decision version of the problem is NP-complete for circle graphs, the complexity of the problem differs from that of the secure domination problem, and the problem is APX-complete for graphs of degree at most 4. Furthermore, we show that the optimization version of the problem on bipartite graphs cannot be approximated in polynomial time within (1 - epsilon)ln | V | for any epsilon > 0, unless NP & SUBE;Dtime(|V |(O (log log |V |))). (c) 2022 Elsevier B.V. All rights reserved.

关键词： Secure total dominating set linear-time algorithm NP-complete APX-complete

来源：评论

学校读者我要写书评

暂无评论

Hierarchical Gaussian Markov Random Field for Image Denoising

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2022年第3期E105D卷 689-699页

作者： Monma, Yuki Aro, Kan Yasuda, Muneki Yamagata Univ Grad Sch Sci & Engn Yonezawa Yamagata 9928510 Japan Diamond Head Co Ltd Sapporo Hokkaido 0600001 Japan

In this study, Bayesian image denoising, in which the prior distribution is assumed to be a Gaussian Markov random field (GMRF), is considered. Recently, an effective algorithm for Bayesian image denoising with a standard GMRF prior has been proposed, which can help implement the overall procedure and optimize its parameters in O(n)-time, where n is the size of the image. A new GMRF-type prior, referred to as a hierarchical GMRF (HGMRF) prior, is proposed, which is obtained by applying a hierarchical Bayesian approach to the standard GMRF prior;in addition, an effective denoising algorithm based on the HGMRF prior is proposed. The proposed HGMRF method can help implement the overall procedure and optimize its parameters in 0(n)-time, as well as the previous GMRF method. The restoration quality of the proposed method is found to be significantly higher than that of the previous GMRF method as well as that of a non-local means filter in several cases. Furthermore, numerical evidence implies that the proposed HGMRF prior is more suitable for the image prior than the standard GMRF prior.

关键词： Bayesian image denoising Gaussian Markov random field hierarchical Bayes method linear-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Finding Hamiltonian cycles of truncated rectangular grid graphs in linear time

引用

APPLIED MATHEMATICS AND COMPUTATION 2023年 436卷

作者： Keshavarz-Kohjerdi, Fatemeh Bagheri, Alireza Shahed Univ Dept Comp Sci Tehran Iran Amirkabir Univ Technol Dept Comp Engn Tehran Iran

The Hamiltonian cycle problem is an important problem in graph theory. For solid grid graphs, an O(n(4))-time algorithm has been given. In this paper, we solve the problem for a special class of solid grid graphs, i.e... 详细信息

关键词： Hamiltonian cycle problem Solid grid graph Truncated rectangular grid graphs linear-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimum Maximal Acyclic Matching in Proper Interval Graphs 9th

Minimum Maximal Acyclic Matching in Proper Interval Graphs

引用

9th International Conference on algorithms and Discrete Applied Mathematics (CALDAM)

作者： Chaudhary, Juhi Mishra, Sounaka Panda, B. S. Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel Indian Inst Technol Madras Dept Math Chennai India Indian Inst Technol Delhi Dept Math New Delhi India

ISBN: (纸本)9783031252105;9783031252112

Given a graph G, MIN-MAX-ACY-MATCHING is the problem of finding a maximal matching M in G of minimum cardinality such that the set of M-saturated vertices induces an acyclic subgraph in G. The decision version of MIN-MAX-ACY-MATCHING is known to be NP-complete even for planar perfect elimination bipartite graphs. In this paper, we give the first positive algorithmic result for MIN-MAX-ACY-Matching by presenting a linear-time algorithm for computing a minimum cardinality maximal acyclic matching in proper interval graphs.

关键词： Matching Acyclic matching Minimum maximal acyclic matching linear-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Edge open packing: Complexity, algorithmic aspects, and bounds

引用

THEORETICAL COMPUTER SCIENCE 2024年 1022卷

作者： Bresar, Bostjan Samadi, Babak Univ Maribor Fac Nat Sci & Math Maribor Slovenia Inst Math Phys & Mech Ljubljana Slovenia

Given a graph G, two edges e(1), e(2) is an element of E(G) said to have a common edge e not equal e(1), e(2) if e joins an endvertex of e(1) to an endvertex of e(2). A subset B subset of E(G) is an edge open packing set in G if no two edges of B have a common edge in G, and the maximum cardinality of such a set in G is called the edge open packing number, p(e)(o)(G) of G. In this paper, we prove that the decision version of the edge open packing number is NP-complete even when restricted to graphs with universal vertices, Eulerian bipartite graphs, and planar graphs with maximum degree 4, respectively. In contrast, we present a linear-time algorithm that computes the edge open packing number of a tree. We also resolve two problems posed in the seminal paper (Chelladurai et al. (2022) [5]). Notably, we characterize the graphs G that attain the upper bound p(e)(o)(G) <= |E(G)|/delta(G), and provide lower and upper bounds for the edge-deleted subgraph of a graph and establish the corresponding realization result.

关键词： Edge open packing NP-complete linear-time algorithm Independent set

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：