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

Unique Response Roman Domination: Complexity and algorithms

algorithmICA 2023年第12期85卷 3889-3927页

作者： Banerjee, Sumanta Chaudhary, Juhi Pradhan, Dinabandhu Indian Inst Technol ISM Dept Math & Comp Dhanbad India Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

A function f : V( G) ->{0, 1, 2} is called a Roman dominating function on G = ( V(G), E(G)) if for every vertex v with f (v) = 0, there exists a vertex u epsilon N-G(v) such that f (u) = 2. A function f : V(G). {0, 1, 2} induces an ordered partition ( V-0, V-1, V-2) of V( G), where V-i = {v epsilon V( G) : f (v) = i} for i epsilon{0, 1, 2}. A function f : V(G)->{0, 1, 2} with ordered partition ( V-0, V-1, V-2) is called a unique response Roman function if for every vertex v with f (v) = 0, | N-G(v) boolean AND V-2| <= 1, and for every vertex v with f (v) = 1 or 2, | N-G(v) boolean AND V-2| = 0. A function f : V(G)->{0, 1, 2} is called a unique response Roman dominating function (URRDF) on G if it is a unique response Roman function as well as a Roman dominating function on G. The weight of a unique response Roman dominating function f is the sum f ( V(G)) = Sigma (v epsilon V(G)) f (v), and the minimum weight of a unique response Roman dominating function on G is called the unique response Roman domination number of G and is denoted by u(R)(G). Given a graph G, the Min- URRDF problem asks to find a unique response Roman dominating function of minimum weight on G. In this paper, we study the algorithmic aspects of Min- URRDF. We show that the decision version of Min- URRDF remains NP-complete for chordal graphs and bipartite graphs. We show that for a given graph with n vertices, Min- URRDF cannot be approximated within a ratio of n(1-epsilon) for any epsilon > 0 unless P = NP. We also show that Min- URRDF can be approximated within a factor of Delta + 1 for graphs having maximum degree Delta. On the positive side, we design a linear-time algorithm to solve Min- URRDF for distance-hereditary graphs. Also, we show that Min- URRDF is polynomial-time solvable for interval graphs, and strengthen the result by showing that Min- URRDF can be solved in linear-time for proper interval graphs, a proper subfamily of interval graphs.

关键词： Domination Roman domination Unique response Roman function Unique response Roman domination polynomial-time algorithm NP-completeness

来源：评论

学校读者我要写书评

暂无评论

Path norms on a matrix

引用

SOFT COMPUTING 2023年第11期27卷 6939-6959页

作者： Varsha Aishwarya, S. Kuncham, Syam Prasad Kedukodi, Babushri Srinivas Manipal Acad Higher Educ MAHE Manipal Inst Technol Dept Math Manipal 576104 Karnataka India

We define row path norm and column path norm of a matrix and relate path norms with other standard matrix norms. A row (resp. column) path norm gives a path that maximizes relative row (resp. column) distances starting from the first row (resp. column). The comparison takes place from the last row (resp. column) to the first row (resp. column), tracing the path. We categorize different versions of path norms and provide algorithms to compute them. We show that brute-force methods to compute path norms have exponential running time. We give dynamic programming algorithms, which, in contrast, take quadratic running time for computing the path norms. We define path norms on Church numerals and Church pairs. Finally, we present applications of path norms in computing condition number, and ordering the solutions of magic squares and Latin squares

关键词： Matrix norm Matrix seminorm Normed ring polynomial-time algorithm Church numerals

来源：评论

学校读者我要写书评

暂无评论

Best Match Graphs With Binary Trees

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2023年第3期20卷 1679-1690页

作者： Schaller, David Geiss, Manuela Hellmuth, Marc Stadler, Peter F. F. Max Planck Inst Math Sci D-04103 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinformat Dept Comp Sci Bioinformat Grp D-04107 Leipzig Germany Software Competence Ctr Hagenberg GmbH A-4232 Hagenberg Austria Stockholm Univ Fac Sci Dept Math SE-10691 Stockholm Sweden Univ Vienna Inst Theoret Chem A-1090 Vienna Austria Univ Nacl Colombia Fac Ciencias Sede Bogota Bogota 111321 Colombia Santa Fe Insitute Santa Fe NM 87501 USA

Best match graphs (BMG) are a key intermediate in graph-based orthology detection and contain a large amount of information on the gene tree. We provide a near-cubic algorithm to determine whether a BMG is binary-explainable, i.e., whether it can be explained by a fully resolved gene tree and, if so, to construct such a tree. Moreover, we show that all such binary trees are refinements of the unique binary-refinable tree (BRT), which in general is a substantial refinement of the also unique least resolved tree of a BMG. Finally, we show that the problem of editing an arbitrary vertex-colored graph to a binary-explainable BMG is NP-complete and provide an integer linear program formulation for this task.

关键词： Best match graphs binary trees rooted triple consistency polynomial-time algorithm NP-hardness integer linear program

来源：评论

学校读者我要写书评

暂无评论

Sparse PCA on fixed-rank matrices

引用

MATHEMATICAL PROGRAMMING 2023年第1期198卷 139-157页

作者： Del Pia, Alberto Univ Wisconsin Dept Ind & Syst Engn Madison WI 53706 USA Univ Wisconsin Wisconsin Inst Discovery Madison WI 53706 USA

Sparse PCA is the optimization problem obtained from PCA by adding a sparsity constraint on the principal components. Sparse PCA is NP-hard and hard to approximate even in the single-component case. In this paper we settle the computational complexity of sparse PCA with respect to the rank of the covariance matrix. We show that, if the rank of the covariance matrix is a fixed value, then there is an algorithm that solves sparse PCA to global optimality, whose running time is polynomial in the number of features. We also prove a similar result for the version of sparse PCA which requires the principal components to have disjoint supports.

关键词： Principal component analysis Sparsity polynomial-time algorithm Global optimum Constant-rank quadratic function

来源：评论

学校读者我要写书评

暂无评论

polynomial algorithms to Minimize 2/3-Submodular Functions 25th

Polynomial Algorithms to Minimize 2/3-Submodular Functions

引用

25th International Conference on Integer Programming and Combinatorial Optimization (IPCO)

作者： Mizutani, Ryuhei Yoshida, Yuki Univ Tokyo Tokyo 1138656 Japan

ISBN: (纸本)9783031598340;9783031598357

It is a fundamental result in combinatorial optimization that submodular functions can be minimized in polynomial-time. This paper considers the minimization problem for a more general class of set functions that contains all submodular functions. A set function is called 2/3-submodular if the submodular inequality holds for at least two pairs formed from every distinct three subsets. This paper provides two weakly polynomial-time algorithms to minimize 2/3-submodular functions, which yield an efficient algorithm to obtain color assignments of a variant of the supermodular coloring theorem.

关键词： 2/3-submodular function polynomial-time algorithm Supermodular coloring

来源：评论

学校读者我要写书评

暂无评论

polynomial-time algorithms for Path Movement Problems on Trees and Unicyclic Graphs

引用

JOURNAL OF INTERNET TECHNOLOGY 2019年第6期20卷 1729-1735页

作者： Chouvatut, Varin Jindaluang, Wattana Chiang Mai Univ Dept Comp Sci Chiang Mai Thailand

In the path movement problem, we are given an undirected graph G = (V, E), a source vertex s, a destination vertex t, and a set of movable objects, called pebbles, which are placed on a subset of the vertices of a graph. We want to move a subset of the pebbles along the edges to a subset of the vertices of the graph such that there exists a path from s to t in graph G in such a way that all the vertices in that path are occupied by at least one pebble. The PathMax and the PathSum problems are the path movement problems in which we want to minimize the maximum movements and the total movements made by the pebbles, respectively. In [7], the researchers proved that both the problems are NP-hard in general graphs. In this paper, the PathMax and the PathSum problems are considered on special classes of graph G, that is, G is a tree and a unicyclic graph. More precisely, this paper shows that PathMax and PathSum problems can be easily solved in polynomial time when the input graph is a tree or a unicyclic graph.

关键词： polynomial-time algorithm Movement problem Tree Unicyclic graph

来源：评论

学校读者我要写书评

暂无评论

Graph Bipartization Problem with Applications to Via Minimization in VLSI Design

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2023年第4期34卷 347-361页

作者： Lin, Lan Lin, Yixun Tongji Univ Sch Elect & Informat Engn Shanghai 200092 Peoples R China Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Peoples R China

The bipartization problem for a graph G asks for finding a subset S of V(G) such that the induced subgraph G[S] is bipartite and vertical bar S vertical bar is maximized. This problem has significant applications in the via minimization of VLSI design. The problem has been proved NP-complete and the fixed parameter solvability has been known in the literature. This paper presents several polynomial-time algorithms for special graph families, such as split graphs, co-bipartite graphs, chordal graphs, and permutation graphs.

关键词： Bipartite induced subgraph odd-cycle transversal via minimization VLSI design polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

On Fixed-Parameter Solvability of the Minimax Path Location Problem

引用

Communications on Applied Mathematics and Computation 2023年第4期5卷 1644-1654页

作者： Hao Lin Cheng He School of Science Henan University of TechnologyZhengzhou450001HenanChina

The minimax path location problem is to find a path P in a graph G such that the maximum distance d_(G)(v,P)from every vertex v∈V(G)to the path P is *** is a well-known NP-hard problem in network *** paper studies the fixed-parameter solvability,that is,for a given graph G and an integer k,to decide whether there exists a path P in G such that max v∈V(G)d_(G)(v,P)≤*** the answer is affirmative,then graph G is called *** show that this decision problem is NP-complete even for k=*** the other hand,we characterize the family of 1-path-eccentric graphs,including the traceable,interval,split,permutation graphs and ***,some polynomially solvable special graphs are discussed.

关键词： Discrete location Path location Fixed-parameter solvability Graph characterization polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Axiomatization of Implication for Probabilistic Independence and Unary Variants of Marginal Identity and Marginal Distribution Equivalence 13th

Axiomatization of Implication for Probabilistic Independence...

引用

13th International Symposium on Foundations of Information and Knowledge Systems (FoIKS)

作者： Hirvonen, Minna Univ Helsinki Dept Math & Stat Helsinki Finland

ISBN: (纸本)9783031569395;9783031569401

We consider probabilistic independence and unary variants of marginal identity and marginal distribution equivalence over finite probability distributions. Two variables x and y satisfy a unary marginal identity when they are identically distributed. If the multisets of the marginal probabilities of all possible values for variables x and y are equal, the variables satisfy a unary marginal distribution equivalence. This paper offers a sound and complete finite axiomatization and a polynomial-time algorithm for the implication problem for probabilistic independence, unary marginal identity, and unary marginal distribution equivalence.

关键词： Complete axiomatization Probabilistic independence Marginal distribution equivalence Marginal identity polynomial-time algorithm Probabilistic team semantics

来源：评论

学校读者我要写书评

暂无评论

Fast algorithm for the Rainbow Disconnection Coloring of 2-Trees

引用

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA 2023年 1-13页

作者： Bai, Xu-Qing Li, Bi Xu, Chuan-Dong Zhang, Xin Xidian Univ Sch Math & Stat Xian 710071 Shaanxi Peoples R China

Given a connected graph G = (V, E), a rainbow disconnection k-coloring of G is a k-edge coloring of G such that for each pair of vertices u, v is an element of V, there is a rainbow (edge) cut of u, v, which is a subset RC(u, v)subset of E such that u, v are disconnected in G\RC(u, v) and that all edges in RC(u, v) have different colors. Theminimum integer k such that G admits a rainbow disconnection k-coloring is the rainbow disconnection number of G, denoted by rd(G). It has been shown that rd( G) is closely related to the maximum number lambda(+) ( G) of edge disjoint paths among all pairs of vertices in G. In this paper, we propose a polynomial-time algorithm for finding a rainbow disconnection rd(G)-coloring of a 2-tree, a graph G formed by starting with a triangle and then repeatedly adding vertices in such a way that each added vertex is adjacent to two ends of an edge. Moreover, the algorithm shows that rd(G) = lambda(+) (G) if G is a 2-tree. This justifies a conjecture of Bai et al. [MR4385957] in 2-trees, which states that rd( G) is either lambda(+) (G) or lambda(+) (G) + 1 for each graph G.

关键词： Rainbow disconnection coloring 2-Tree Dynamic programming polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：