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

Counting independent sets in cocomparability graphs

INFORMATION PROCESSING LETTERS 2019年 144卷 31-36页

作者： Dyer, Martin Mueller, Haiko Univ Leeds Sch Comp Leeds LS2 9JT W Yorkshire England

We show that the number of independent sets in cocomparability graphs can be counted in linear time, as can counting cliques in comparability graphs. By contrast, counting cliques in cocomparability graphs and counting independent sets in comparability graphs are #P-complete. We extend these results to counting maximal cliques and independent sets. We also consider the fixed-parameter versions of counting cliques and independent sets of given size k. Finally, we combine the results to show that both counting cliques and independent sets in permutation graphs are in linear time. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Cocomparability graph Independent set Counting linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

Genomic distance under gene substitutions

引用

BMC BIOINFORMATICS 2011年第Sup9期12卷 1-9页

作者： Braga, Marilia D. V. Machado, Raphael Ribeiro, Leonardo C. Stoye, Jens Inst Nacl Metrol Qualidade & Tecnol BR-25250020 Duque De Caxias Brazil Univ Bielefeld Tech Fak AG Genominformat D-33594 Bielefeld Germany

Background: The distance between two genomes is often computed by comparing only the common markers between them. Some approaches are also able to deal with non-common markers, allowing the insertion or the deletion of such markers. In these models, a deletion and a subsequent insertion that occur at the same position of the genome count for two sorting steps. Results: Here we propose a new model that sorts non-common markers with substitutions, which are more powerful operations that comprehend insertions and deletions. A deletion and an insertion that occur at the same position of the genome can be modeled as a substitution, counting for a single sorting step. Conclusions: Comparing genomes with unequal content, but without duplicated markers, we give a linear time algorithm to compute the genomic distance considering substitutions and double-cut-and-join (DCJ) operations. This model provides a parsimonious genomic distance to handle genomes free of duplicated markers, that is in practice a lower bound to the real genomic distances. The method could also be used to refine orthology assignments, since in some cases a substitution could actually correspond to an unannotated orthology.

关键词： linear time algorithm Adjacency Graph Triangular Inequality Genomic Distance Unique Marker

来源：评论

学校读者我要写书评

暂无评论

Jointly stable matchings

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2019年第2期38卷 646-665页

作者： Miyazaki, Shuichi Okamoto, Kazuya Kyoto Univ Acad Ctr Comp & Media Studies Sakyo Ku Yoshida Honmachi Kyoto 6068501 Japan Kyoto Univ Hosp Div Med Informat Technol & Adm Planning Sakyo Ku 54 Kawaharacho Kyoto 6068507 Japan

In the stable marriage problem, we are given a set of men, a set of women, and each person's preference list. Our task is to find a stable matching, that is, a matching admitting no unmatched (man, woman)-pair each of which improves the situation by being matched together. It is known that any instance admits at least one stable matching. In this paper, we consider a natural extension where k(2) sets of preference lists Li (1ik) over the same set of people are given, and the aim is to find a jointly stable matching, a matching that is stable with respect to all Li. We show that the decision problem is NP-complete for the following two restricted cases;(1) k=2 and each person's preference list is of length at most four, and (2) k=4, each man's preference list is of length at most three, and each woman's preference list is of length at most four. On the other hand, we show that it is solvable in linear time for any k if each man's preference list is of length at most two (women's lists can be of unbounded length). We also show that if each woman's preference lists are same in all Li, then the problem can be solved in linear time.

关键词： Stable marriage problem Stable matching NP-completeness linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

Enhancing distance transform computation by leveraging the discrete nature of images

引用

JOURNAL OF REAL-time IMAGE PROCESSING 2022年第4期19卷 763-773页

作者： Fuseiller, Guillaume Marie, Romain Mourioux, Gilles Duno, Erick Labbani-Igbida, Ouiddad Univ Limoges XLim Inst UMR CNRS 7252 16 Rue Atlantis F-87068 Limoges France VALEO Mat Frict Limoges France 3iL Grp 43 Rue St Anne F-87015 Limoges France

This paper presents a major reformulation of a widely used solution for computing the exact Euclidean distance transform of n-dimensional discrete binary shapes. Initially proposed by Hirata, the original algorithm is linear in time, separable, and easy to implement. Furthermore, it accounts for the fastest existing solutions, leading to its widespread use in the state of the art, especially in real-time applications. In particular, we focus on the second step of this algorithm, where the lower envelope of a set of parabolas has to be computed. By leveraging the discrete nature of images, we show that some of those parabolas can be merged into line segments. It reduces the computational cost of the algorithm by about 20% in most practical cases, while maintaining its exactness. To evaluate the proposed improvement on different cases, two state-of-the art benchmarks are implemented and discussed.

关键词： Distance transform linear time algorithm Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

A Systematic algorithm for Identifying Faults on Hypercube-Like Networks Under the Comparison Model

引用

IEEE TRANSACTIONS ON RELIABILITY 2012年第2期61卷 452-459页

作者： Lai, Pao-Lien Natl Dong Hwa Univ Dept Comp Sci & Informat Engn Shoufeng 97401 Hualien Taiwan

There is a growing demand for fault diagnosis to increase the reliability of systems. Diagnosis by comparison is a realistic approach to the fault diagnosis of multiprocessor systems. In this paper, we consider n-dimensional hypercube-like networks for n >= 5 We propose an efficient fault diagnosis algorithm for n-dimensional hypercube-like networks under the MM comparison model by exploiting the Hamiltonian and extended-star properties. Applying our algorithm, the faulty processors in n-dimensional hypercubes, n-dimensional crossed cubes, n-dimensional twisted cubes, and n-dimensional Mobius cubes can all be diagnosed in linear time provided the number of faulty processors is not more than the dimension n.

关键词： Comparison model extended star Hamiltonian hypercube-like networks linear time algorithm t-diagnosable

来源：评论

学校读者我要写书评

暂无评论

A simple recognition of maximal planar graphs

引用

INFORMATION PROCESSING LETTERS 2004年第5期89卷 223-226页

作者： Nagamochi, H Suzuki, T Ishii, T Toyohashi Univ Technol Dept Informat & Comp Sci Toyohashi Aichi 4418580 Japan Star Micron Co Ltd Shizuoka 4228654 Japan

In this paper, we consider the problem of determining whether a given graph is a maximal planar graph or not. We show that a simple linear time algorithm can be designed based on canonical orderings. Our algorithm needs no sophisticated data structure and is significantly easy to implement compared with the existing planarity testing algorithms. (C) 2003 Elsevier B.V. All rights reserved.

关键词： linear time algorithm maximal planar graph triangulated plane graph planarity test graph algorithms

来源：评论

学校读者我要写书评

暂无评论

The k-power domination problem in weighted trees

引用

THEORETICAL COMPUTER SCIENCE 2020年 809卷 231-238页

作者： Cheng, Changjie Lu, Changhong Zhou, Yu East China Normal Univ Sch Math Sci Shanghai Key Lab PMMP Shanghai 200291 Peoples R China

The power domination problem of the graph comes from how to choose the node location of the least phase measurement units in the electric power system. In the actual electric power system, because of the difference in the cost of phase measurement units at different nodes, it is more practical to study the power domination problem with the weighted graph. In this paper, we present a dynamic programming style linear-time algorithm for k-power domination problem in weighted trees. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Power domination Weighted trees linear time algorithm Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Labelled packing functions in graphs

引用

INFORMATION PROCESSING LETTERS 2020年 154卷 105863-000页

作者： Hinrichsen, Erica G. Leoni, Valeria A. Safe, Martin D. Univ Nacl Rosario Dept Matemat Rosario Santa Fe Argentina Consejo Nacl Invest Cient & Tecn Buenos Aires DF Argentina Univ Nacl Sur Dept Matemat Bahia Blanca Buenos Aires Argentina Univ Nacl Sur CONICET INMABB Bahia Blanca Buenos Aires Argentina

Given a positive integer k and a graph G, a k-limited packing in G is a subset B of its vertex set such that each closed vertex neighborhood of G has at most k vertices of B (Gallant et al., 2010). A first generalization of this concept deals with a subset of vertices that cannot be in the set B and also, the number k is not a constant but it depends on the vertex neighborhood (Dobson et al., 2010). As another variation, a (k}-packing function f of G assigns a non-negative integer to the vertices of G in such a way that the sum of the values of f over each closed vertex neighborhood is at most k (Hinrichsen et al., 2014). The three associated decision problems are NP-complete in the general case. We introduce L-packing functions as a unified notion that generalizes all limited packing concepts introduced up to now. We present a linear time algorithm that solves the problem of finding the maximum weight of an L-packing function in strongly chordal graphs when a strong elimination ordering is given that includes the linear algorithm for {k}-packing functions in strongly chordal graphs (2014). Besides, we show how the algorithm can be used to solve the known clique-independence problem on strongly chordal graphs in linear time (G. Chang et al., 1993). (C) 2019 Published by Elsevier B.V.

关键词： Computational complexity Labelled packing problem Strongly chordal graph linear time algorithm Clique-independence

来源：评论

学校读者我要写书评

暂无评论

WEIGHTED EFFICIENT DOMINATION FOR P₅-FREE AND P₆-FREE GRAPHS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2016年第4期30卷 2288-2303页

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

In a finite undirected graph G = (V, E), a vertex v is an element of V dominates itself and its neighbors in G. A vertex set D subset of V is an efficient dominating set (e.d.s. for short) of G if every v 2 V is dominated in G 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 for P-7-free graphs and solvable in polynomial time for P-5-free graphs. The P-6-free case was the last open question for the complexity of ED on F-free graphs. Recently, Lokshtanov, Pilipczuk, and van Leeuwen showed that weighted ED is solvable in polynomial time for P-6-free graphs, based on their quasi-polynomial algorithm for the Maximum Weight Independent Set problem for P-6-free graphs. Independently, by a direct approach which is simpler and faster, we found an O(n(5)m) time solution for weighted ED on P-6-free graphs. Moreover, we show that weighted ED is solvable in linear time for P-5-free graphs which solves another open question for the complexity of (weighted) ED. The result for P-5-free graphs is based on modular decomposition.

关键词： weighted efficient domination P-5-free graphs P-6-free graphs polynomial time algorithm linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient Euclidean distance transform algorithm of binary images in arbitrary dimensions

引用

PATTERN RECOGNITION 2013年第1期46卷 230-242页

作者： Wang, Jun Tan, Ying Peking Univ Sch Elect Engn & Comp Sci Dept Machine Intelligence Beijing 100871 Peoples R China Peking Univ Key Lab Machine Percept MOE Beijing 100871 Peoples R China State Adm Taxat Shandong Prov Off Jinan Peoples R China

In this paper, we propose an efficient algorithm, i.e., PBEDT, for short, to compute the exact Euclidean distance transform (EDT) of a binary image in arbitrary dimensions. The PBEDT is based on independent scan and implemented in a recursive way, i.e., the EDT of a d-dimensional image is able to be computed from the EDTs of its (d-1)-dimensional sub-images. In each recursion, all of the rows in the current dimensional direction are processed one by one. The points in the current processing row and their closest feature points in (d-1)-dimensional sub-images can be shown in a Euclidean plane. By using the geometric properties of the perpendicular bisector, the closest feature points of (d-1)-dimensional subimages are easily verified so as to lead to the EDT of a d-dimensional image after eliminating the invalid points. The time complexity of the PBEDT algorithm is linear in the amount of both image points and dimensions with a small coefficient. Compared with the state-of-the-art EDT algorithms, the PBEDT algorithm is much faster and more stable in most cases. (C) 2012 Elsevier Ltd. All rights reserved.

关键词： Euclidean distance transform Arbitrary dimensions Independent scan linear time algorithm Binary image

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：