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

On computing a minimum secure dominating set in block graphs

JOURNAL OF COMBINATORIAL OPTIMIZATION 2018年第2期35卷 613-631页

作者： Pradhan, D. Jha, Anupriya Indian Inst Technol Dept Appl Math Dhanbad Bihar India

In a graph , a set is said to be a dominating set of G if for every vertex , there exists a vertex such that . A secure dominating set of the graph G is a dominating set D of G such that for every , there exists a vertex such that and is a dominating set of G. Given a graph G and a positive integer k, the secure domination problem is to decide whether G has a secure dominating set of cardinality at most k. The secure domination problem has been shown to be NP-complete for chordal graphs via split graphs and for bipartite graphs. In Liu et al. (in: Proceedings of 27th workshop on combinatorial mathematics and computation theory, 2010), it is asked to find a polynomial time algorithm for computing a minimum secure dominating set in a block graph. In this paper, we answer this by presenting a linear time algorithm to compute a minimum secure dominating set in block graphs. We then strengthen the known NP-completeness of the secure domination problem by showing that the secure domination problem is NP-complete for undirected path graphs and chordal bipartite graphs.

关键词： Domination Secure domination Block graphs linear time algorithm NP-complete

来源：评论

学校读者我要写书评

暂无评论

Fast smoothing technique with edge preservation for single image dehazing

引用

IET COMPUTER VISION 2015年第6期9卷 950-959页

作者： Wang, Dan Zhu, Jubo Natl Univ Def Technol Coll Sci Changsha Hunan Peoples R China

In the single-image dehazing problem, it is critical that the transmission is accurately estimated. However, the extracted transmission in the dark channel model cannot effectively deal with the edge and the sky area because of the poor applicability of the dark channel prior to these areas. This study aims to solve that problem by proposing a novel variational model (VM) to optimise the transmission. This VM introduces a smoothness term and a gradient-preserving term to mitigate the false edge and the distorted sky area in the recovered image. Further, a fast algorithm to solve the VM is proposed on the basis of the additional operator splitting algorithm. This algorithm is an effective linear time algorithm and has excellent performance on optimising the transmission. The average running time of the algorithm shows an improvement of over 20 times that of the guided image filtering in these experiments. Experimental results also show that the proposed algorithm is both effective and efficient for optimising the transmission.

关键词： smoothing methods edge detection image filtering optimisation variational techniques computational complexity edge preservation single image dehazing variational model transmission optimisation VM smoothness gradient preservation distorted sky area mitigation false edge mitigation additional operator splitting algorithm linear time algorithm guided image filtering smoothing technique

来源：评论

学校读者我要写书评

暂无评论

algorithms for Connected Component Labeling Based on Quadtrees

引用

INTERNATIONAL JOURNAL OF IMAGING SYSTEMS AND TECHNOLOGY 2009年第2期19卷 158-166页

作者： Aizawa, Kunio Tanaka, Shojiro Motomura, Koyo Kadowaki, Ryosuke Shimane Univ Dept Math & Comp Sci Interdisciplinary Fac Sci & Engn Matsue Shimane 6908502 Japan Shimane Univ Dept Math & Comp Sci Interdisciplinary Grad Sch Sci & Engn Matsue Shimane 6908502 Japan

An algorithm of linear time complexity is presented to label connected components of a binary image by a quadtree. For a given node, the search for all adjacent nodes is carried out in O(1) (i.e., constant time complexity for the worst case) using our formerly presented algorithm in (Aizawa et al., 3rd International Symposium on Communications, Control, and Signal Processing, 2008, 505-510), whereas it explores all possible adjacencies for each node in a usual way. Then during the process of tree formulation in the search, all equivalent relations of labels are stored as lists. time complexity of the algorithm is O(B+W) for the worst case and its auxiliary space is no more than O(B), where B and W correspond to the number of leaf nodes in a quadtree representing black and white quadrants, respectively. Empirical tests of the algorithm are employed in comparison with another linear time connected component labeling algorithm based on top-down quadtree traversal algorithm (Samet, IEEE Trans Pattern Anal Mach Intell PAMI-7 (1985), 94-98), as well as traditional row-by-row scanning algorithm using linear time Union-Find (Fiorio and Gustedt, Theor Comput Sci 154 (1996), 165-181). Our algorithm has shown the best performance in large images. (C) 2009 Wiley Periodicals, Inc. Int J Imaging Syst Technol, 19, 158-166, 20091, Published online in Wiley InterScience (***). DOI 10.1002/ima.20179

关键词： adjacency search digital image dilated integer linear quadtree linear time algorithm Union-Find problem

来源：评论

学校读者我要写书评

暂无评论

The d-precoloring problem for k-degenerate graphs

引用

DISCRETE MATHEMATICS 2007年第16期307卷 2042-2052页

作者： Chlebikova, Janka Jansen, Klaus Comenius Univ Fac Math Phys & Informat Bratislava 84248 Slovakia Univ Kiel Inst Informat & Prakt Math D-24098 Kiel Germany

In this paper we deal with the d-PRECOLORING EXTENSION (d-PREXT) problem in various classes of graphs. The d-PREXT problem is the special case of PRECOLORING EXTENSION problem where, for a fixed constant d, input instances are restricted to contain at most d precolored vertices for every available color. The goal is to decide if there exists an extension of given precoloring using only available colors or to find it. We present a linear time algorithm for both, the decision and the search version of d-PREXT, in the following cases: (i) restricted to the class of k-degenerate graphs (hence also planar graphs) and with sufficiently large set S of available colors, and (ii) restricted to the class of partial k-trees (without any size restriction on S). We also study the following problem related to d-PREXT: given an instance of the d-PREXT problem which is extendable by colors of S, what is the minimum number of colors of S sufficient to use for precolorless vertices over all such extensions? We establish lower and upper bounds on this value for k-degenerate graphs and its various subclasses (e.g., planar graphs, outerplanar graphs) and prove tight results for the class of trees. (c) 2006 Elsevier B.V. All rights reserved.

关键词： PRECOLORING EXTENSION problem linear time algorithm k-degenerate graphs partial k-trees

来源：评论

学校读者我要写书评

暂无评论

SHORTEST POLYGONAL PATHS IN SPACE

引用

COMPUTING 1990年第1期45卷 51-68页

作者： BURKARD, RE ROTE, G YAO, EY YU, ZL ZHEJIANG UNIV DEPT MATH HANGZHOU PEOPLES R CHINA FORESTRY UNIV NANJING MATH SECT NANJING PEOPLES R CHINA

A classical problem of geometry is the following: given a convex polygon in the plane, find an inscribed polygon of shortest circumference. In this paper we generalize this problem to arbitrary polygonal paths in space and consider two cases: in the “open” case the wanted path of shortest length can have different start and end point, whereas in the “closed” case these two points must coincide. We show that finding such shortest paths can be reduced to finding a shortest path in a planar “channel”. The latter problem can be solved by an algorithm of linear-time complexity in the open as well in the closed case. Finally, we deal with constrained problems where the wanted path has to fulfill additional properties; in particular, if it has to pass straight through a further point, we show that the length of such a constrained polygonal path is a strictly convex function of some angle α, and we derive an algorithm for determining such constrained polygonal paths efficiently.

关键词： 68U05 90C25 Shortest polygonal paths shortest inpolygons funnel linear time algorithm constrained paths convex function

来源：评论

学校读者我要写书评

暂无评论

On a class of graphs between threshold and total domishold graphs

引用

DISCRETE APPLIED MATHEMATICS 2015年 195卷 43-58页

作者： Chiarelli, Nina Milanic, Martin Univ Primorska Fac Math Nat Sci & Informat Technol Koper SI-6000 Slovenia Univ Primorska Andrej Marusic Inst SI-6000 Koper Slovenia

A total dominating set in a graph is a subset of vertices such that every vertex in the graph has a neighbor in it. A graph is said to be total domishold if it admits a total domishold structure, that is, a hyperplane with non-negative coefficients that separates the characteristic vectors of its total dominating sets from the characteristic vectors of other vertex subsets. Hereditary total domishold graphs, that is, graphs every induced subgraph of which is total domishold, were recently characterized in terms of forbidden induced subgraphs;this characterization leads to an O(vertical bar V(G)vertical bar(6)) recognition algorithm of hereditary total domishold graphs. In this paper, we study a subclass g of the hereditary total domishold graphs obtained by replacing two of the forbidden induced subgraphs of order 6 with two of their proper induced subgraphs of order 5. We show that every connected graph in 9, is a leaf extension of a threshold graph, that is, it can be obtained from some threshold graph G by attaching some pendant vertices to each vertex of G. Using this property, we develop a structural characterization of graphs in g, which implies a linear time recognition algorithm for graphs in this class. We also give a linear time algorithm for computing a total domishold structure of a graph in g. In contrast to the algorithm for the general case of (hereditary) total domishold graphs, which relies on solving a linear program, our algorithm is purely combinatorial and works directly with the graph. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Total domination Total domishold graph Threshold graph Forbidden induced subgraph characterization linear time algorithm Leaf extension of a threshold graph

来源：评论

学校读者我要写书评

暂无评论

Correcting the algorithm for a minimum secure dominating set of proper interval graphs by Zou, Liu, Hsu and Wang

引用

DISCRETE APPLIED MATHEMATICS 2023年第1期334卷 139-144页

作者： Araki, Toru Saito, Ryuya Gunma Univ Grad Sch Sci & Technol Kiryu Gunma 3768515 Japan Gunma Univ Div Elect & Informat Kiryu Gunma Japan

Zou et al. (2019) proposed an algorithm for calculating a minimum secure dominating set of a proper interval graph. However, we find a counterexample for which the algorithm outputs an incorrect subset of vertices. In... 详细信息

关键词： Secure domination Domination Proper interval graphs linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

Computing square roots of trivially perfect and threshold graphs

引用

DISCRETE APPLIED MATHEMATICS 2013年第10-11期161卷 1538-1545页

作者： Milanic, Martin Schaudt, Oliver Univ Primorska UP IAM SI-6000 Koper Slovenia Univ Primorska UP FAMNIT SI-6000 Koper Slovenia Univ Cologne Dept Comp Sci D-50931 Cologne Germany

A graph H is a square root of a graph G if two vertices are adjacent in G if and only if they are at distance one or two in H. Computing a square root of a given graph is NP-hard, even when the input graph is restricted to be chordal. In this paper, we show that computing a square root can be done in linear time for a well-known subclass of chordal graphs, the class of trivially perfect graphs. This result is obtained by developing a structural characterization of graphs that have a split square root. We also develop linear time algorithms for determining whether a threshold graph given either by a degree sequence or by a separating structure has a square root. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Square of a graph Square root of a graph Chordal graph Split graph Trivially perfect graph Threshold graph linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

Basic primal infon logic

引用

JOURNAL OF LOGIC AND COMPUTATION 2016年第1期26卷 117-141页

作者： Cotrini, Carlos Gurevich, Yuri Swiss Fed Inst Technol Zurich Switzerland Microsoft Res Bengaluru Karnataka India

Primal infon logic (PIL) was introduced in 2009 in the framework of policy and trust management. In the meantime, some generalizations appeared, and there have been some changes in the syntax of the basic PIL. This article is on the basic PIL, and one of our purposes is to 'institutionalize' the changes. We prove a small-model theorem for the propositional fragment of basic primal infon logic (PPIL), give a simple proof of the PPIL locality theorem and present a linear-time decision algorithm (announced earlier) for PPIL in a form convenient for generalizations. For the sake of completeness, we cover the universal fragment of basic PIL. We wish that this article becomes a standard reference on basic PIL.

关键词： Authorization language basic primal logic DKAL infon logic Kripke semantics linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

A characterization of line graphs that are squares of graphs

引用

DISCRETE APPLIED MATHEMATICS 2014年 173卷 83-91页

作者： Milanic, Martin Oversberg, Andrea Schaudt, Oliver Univ Primorska UP IAM SI-6000 Koper Slovenia Univ Primorska UP FAMNIT SI-6000 Koper Slovenia Univ Cologne Inst Comp Sci D-50931 Cologne Germany Univ Paris 06 Inst Math Jussieu F-75252 Paris France

The square of a graph G, denoted by G(2), is the graph obtained from G by putting an edge between two distinct vertices whenever their distance in G is at most 2. Motwani and Sudan proved that it is NP-complete to decide whether a given graph is the square of some graph. In this paper we give a characterization of line graphs that are squares of graphs, and show that if a line graph is a square, then it is a square of a bipartite graph. As a consequence, we obtain a linear time algorithm for deciding whether a given line graph is the square of some graph. (C) 2014 Elsevier B.V. All rights reserved.

关键词： The square of a graph Line graph linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：