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

THEORETICAL COMPUTER SCIENCE 2019年 796卷 1-21页

作者： Banerjee, S. Keil, J. Mark Pradhan, D. Indian Inst Technol ISM Dept Math & Comp Dhanbad Bihar India Univ Saskatchewan Dept Comp Sci Saskatoon SK Canada

A perfect Roman dominating function on a graph G is a function f : V (G) -> {0,1, 2} having the property that for every vertex u with f (u) = 0, there exists exactly one vertex v such that uv is an element of E(G) and f (v) = 2. The weight of f, denoted by w(f), is the value Sigma(v is an element of v(G)) f (v). Given a graph G and a positive integer k, the perfect Roman domination problem is to decide whether there is a perfect Roman dominating function f on G such that w(f) is at most k. In this paper, we first show that the perfect Roman domination problem is NP-complete for chordal graphs, planar graphs, and bipartite graphs. Then we present polynomial time algorithms for computing a perfect Roman dominating function with minimum weight in block graphs, cographs, series-parallel graphs, and proper interval graphs. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Domination Roman domination Perfect Roman domination polynomial time algorithm NP-complete

来源：评论

学校读者我要写书评

暂无评论

The proper vertex-disconnection of graphs

引用

THEORETICAL COMPUTER SCIENCE 2022年 923卷 167-178页

作者： Chen, You Li, Xueliang Nankai Univ Ctr Combinator Tianjin 300071 Peoples R China Nankai Univ LPMC Tianjin 300071 Peoples R China

Let Gbe a vertex-colored connected graph. A subset X of the vertex-set of G is called proper if any two adjacent vertices in X have distinct colors. The graph G is called proper vertex-disconnected if for any two vertices x and y of G, there exists a vertex subset S of G such that when x and y are nonadjacent, Sis proper and x and y belong to different components of G - S;where as when x and y are adjacent, S + x or S + y is proper and x and y belong to different components of (G - xy) - S. For a connected graph G, the proper vertex-disconnection number of G, denoted by pvd( G), is the minimum number of colors that are needed to make G proper vertex-disconnected. In this paper, we firstly characterize the graphs of order n with proper vertex-disconnection number k for k.{1, n - 2, n - 1, n}. Secondly, we give some sufficient conditions for a graph G such that pvd(G) =.(G), and show that almost all graphs G have pvd(G) =.(G) and pvd(G) =.(G). We also give an equivalent statement of the famous Four Color Theorem. Furthermore, we study the relationship between the proper disconnection number pd(G) of G and the proper vertex-disconnection number pvd(L(G)) of the line graph L(G) of G. Finally, we show that it is NP-complete to decide whether a given vertex-colored graph is proper vertex-disconnected, and it is NP-hard to decide for a fixed integer k = 3, whether the pvd-number of a graph G is no more than k, even if k = 3 and G is a planar graph with Delta(G) = 12. We also show that it is solvable in polynomial time to determine the proper vertex-disconnection number for a graph with maximum degree less than four. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Vertex-coloring Vertex-cut Proper vertex-disconnection Chromatic number NP-complete (hard) polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Tractable Cases of (*,2)-Bounded Parsimony Haplotyping

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2015年第1期12卷 234-247页

作者： Keijsper, Judith Oosterwijk, Tim Tech Univ Eindhoven Dept Math NL-5600 MB Eindhoven Netherlands Maastricht Univ Sch Business & Econ Maastricht Netherlands

Parsimony haplotyping is the problem of finding a set of haplotypes of minimum cardinality that explains a given set of genotypes, where a genotype is explained by two haplotypes if it can be obtained as a combination of the two. This problem is NP-complete in the general case, but polynomially solvable for (k,l)-bounded instances for certain k and l. Here, k denotes the maximum number of ambiguous sites in any genotype, and l is the maximum number of genotypes that are ambiguous at the same site. Only the complexity of the (*,2)-bounded problem is still unknown, where * denotes no restriction. It has been proved that (*,2)-bounded instances have compatibility graphs that can be constructed from cliques and circuits by pasting along an edge. In this paper, we give a constructive proof of the fact that (*,2)-bounded instances are polynomially solvable if the compatibility graph is constructed by pasting cliques, trees and circuits along a bounded number of edges. We obtain this proof by solving a slightly generalized problem on circuits, trees and cliques respectively, and arguing that all possible combinations of optimal solutions for these graphs that are pasted along a bounded number of edges can be enumerated efficiently.

关键词： Drug design hereditary disease health haplotyping graph polynomial time algorithm shortest path matching problem path partition

来源：评论

学校读者我要写书评

暂无评论

Single machine scheduling with slack due dates assignment

引用

ENGINEERING OPTIMIZATION 2017年第4期49卷 709-717页

作者： Liu, Weiguo Hu, Xiangpei Wang, Xuyin Dalian Univ Technol Inst Syst Engn Dalian 116024 Peoples R China Northwest Normal Univ Sch Business Lanzhou Peoples R China

This paper considers a single machine scheduling problem in which each job is assigned an individual due date based on a common flow allowance (i.e. all jobs have slack due date). The goal is to find a sequence for jobs, together with a due date assignment, that minimizes a non-regular criterion comprising the total weighted absolute lateness value and common flow allowance cost, where the weight is a position-dependent weight. In order to solve this problem, an O (n log n) time algorithm is proposed. Some extensions of the problem are also shown.

关键词： Scheduling single machine polynomial time algorithm due date assignment

来源：评论

学校读者我要写书评

暂无评论

Maximizing weighted number of just-in-time jobs on unrelated parallel machines

引用

JOURNAL OF SCHEDULING 2005年第5期8卷 453-460页

作者： Sung, SC Vlach, M Aoyama Gakuin Univ Coll Sci & Engn Dept Ind & Syst Engn Sagamihara Kanagawa 2298551 Japan Kyoto Coll Grad Studies Informat Sakyo Ku Kyoto 6068225 Japan

We are concerned with problems of scheduling jobs non-preemptively with the objective to maximize the weighted number of jobs that are completed exactly at their due dates. It has been shown that the problems for single machine and identical parallel machines are polynomial time solvable. The purpose of this paper is to establish the complexity status of the problem for unrelated parallel machine, which was left open. First, we present a polynomial time algorithm for solving the problem when the number of machine is fixed. Second, we show that when the number of machine is a part of input, the problem becomes NP-hard in the strong sense.

关键词： just-in-time jobs unrelated parallel machines polynomial time algorithm NP-hardness

来源：评论

学校读者我要写书评

暂无评论

Cops and Robbers from a distance

引用

THEORETICAL COMPUTER SCIENCE 2010年第43期411卷 3834-3844页

作者： Bonato, Anthony Chiniforooshan, Ehsan Pralat, Pawel Ryerson Univ Dept Math Toronto ON Canada Univ Western Ontario Dept Comp Sci London ON Canada W Virginia Univ Dept Math Morgantown WV 26506 USA

Cops and Robbers is a pursuit and evasion game played on graphs that has received much attention. We consider an extension of Cops and Robbers, distance k Cops and Robbers, where the cops win if at least one of them is of distance at most k from the robber in G. The cop number of a graph G is the minimum number of cops needed to capture the robber in G. The distance k analogue of the cop number, written c(k)(G), equals the minimum number of cops needed to win at a given distance k. We study the parameter c(k) from algorithmic, structural, and probabilistic perspectives. We supply a classification result for graphs with bounded c(k)(G) values and develop an O(n(2s+3)) algorithm for determining if ck(G) <= s for s fixed. We prove that if s is not fixed, then computing c(k)(G) is NP-hard. Upper and lower bounds are found for c(k)(G) in terms of the order of G. We prove that (n/k)(1/2+o(1)) <= c(k)(n) = O(n/log (2n/k+1) log(k + 2)/k + 1), where c(k)(n) is the maximum of c(k)(G) over all n-vertex connected graphs. The parameter c(k)(G) is investigated asymptotically in random graphs G(n, p) for a wide range of p = p(n). For each k >= 0, it is shown that c(k)(G) as a function of the average degree d(n) = pn forms an intriguing zigzag shape. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Graphs Cop number polynomial time algorithm Strong product NP-hard Random graph

来源：评论

学校读者我要写书评

暂无评论

On efficient domination for some classes of H-free chordal graphs

引用

DISCRETE APPLIED MATHEMATICS 2020年 281卷 81-95页

作者： Brandstadt, Andreas Mosca, Raffaele Univ Rostock Inst Inforrnat D-18051 Rostock Germany Univ G DAnnunzio Dipartimento Econ I-65121 Pescara Italy

A vertex set D in a finite undirected graph G is an efficient dominating set (e.d.s for short) of G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED) problem, which asks for the existence of an e.d.s. in G, is known to be NP-complete even for very restricted graph classes such as for 2P(3)-free chordal graphs while it is solvable in polynomial time for P-6-free chordal graphs (and even for P-6-free graphs). A standard reduction from the NP-complete Exact Cover problem shows that ED is NP-complete for a very special subclass of chordal graphs generalizing split graphs. The reduction implies that ED is NP-complete e.g. for double-gem-free chordal graphs while it is solvable in linear time for gem-free chordal graphs (by various reasons such as bounded clique-width, distance-hereditary graphs, chordal square etc.), and ED is NP-complete for butterfly-free chordal graphs while it is solvable in linear time for 2P(2)-free graphs. We show that (weighted) ED can be solved in polynomial time for H-free chordal graphs when H is net, extended gem, or S-1,S-2,S-3. (c) 2019 Elsevier B.V. All rights reserved.

关键词： Weighted efficient domination H-free chordal graphs NP-completeness Net-free chordal graphs Extended-gem-free chordal graphs S-1,S-2,S-3-free chordal graphs polynomial time algorithm Clique-width

来源：评论

学校读者我要写书评

暂无评论

Computing Explicit Isomorphisms with Full Matrix Algebras over F_q (x)

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2018年第2期18卷 381-397页

作者： Ivanyos, Gabor Kutas, Peter Ronyai, Lajos Hungarian Acad Sci Inst Comp Sci & Control Budapest Hungary Cent European Univ Dept Math & Its Applicat Budapest Hungary Budapest Univ Technol & Econ Dept Algebra Budapest Hungary

We propose a polynomial time f-algorithm (a deterministic algorithm which uses an oracle for factoring univariate polynomials over ) for computing an isomorphism (if there is any) of a finite-dimensional -algebra given by structure constants with the algebra of n by n matrices with entries from . The method is based on computing a finite -subalgebra of which is the intersection of a maximal -order and a maximal R-order, where R is the subring of consisting of fractions of polynomials with denominator having degree not less than that of the numerator.

关键词： Explicit isomorphism Function field Lattice basis reduction Maximal order Full matrix algebra polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

ON THE PROPER-PATH-DECOMPOSITION OF TREES

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 1995年第1期E78A卷 131-136页

作者： TAKAHASHI, A UENO, S KAJITANI, Y Tokyo Inst of Technology Tokyo Japan

We introduce the interval set of a graph G which is a representation of the proper-path-decomposition of G, and show a linear time algorithm to construct an optimal interval set for any tree T. It is shown that a prop... 详细信息

关键词： PROPER-PATH-WIDTH PROPER-PATH-DECOMPOSITION PATH-WIDTH PATH-DECOMPOSITION polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

An O(n plus m) time algorithm for computing a minimum semitotal dominating set in an interval graph

引用

JOURNAL OF APPLIED MATHEMATICS AND COMPUTING 2021年第1-2期66卷 733-747页

作者： Pradhan, D. Pal, Saikat Indian Inst Technol ISM Dept Math & Comp Dhanbad Bihar India

Let G = ( V, E) be a graph without isolated vertices. A set D subset of V is said to be a dominating set of G if for every vertex v is an element of V \ D, there exists a vertex u is an element of D such that uv is an element of E. A set D subset of V is called a semitotal dominating set of G if D is a dominating set and every vertex in D is within distance 2 from another vertex of D. For a given graph G, the semitotal domination problem is to find a semitotal dominating set of G with minimum cardinality. The decision version of the semitotal domination problem is shown to be NP-complete for chordal graphs and bipartite graphs. Henning and Pandey (Theor Comput Sci 766:46-57, 2019) proposed an O(n(2)) time algorithm for computing a minimum semitotal dominating set in interval graphs. In this paper, we show that for a given interval graph G = (V, E), a minimum semitotal dominating set of G can be computed in O(n + m) time, where n = |V| and m = | E|. This improves the complexity of the semitotal domination problem for interval graphs from O(n(2)) to O(n + m).

关键词： Domination Total domination Semitotal domination Interval graphs polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：