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

On the efficiency of polynomial time approximation schemes

INFORMATION PROCESSING LETTERS 1997年第4期64卷 165-171页

作者： Cesati, M Trevisan, L Univ Roma Tor Vergata Dipartimento Informat Sistemi & Prod I-00133 Rome Italy Univ Geneva Ctr Informat CH-1211 Geneva Switzerland

A polynomial time approximation scheme (PTAS) for an optimization problem A is an algorithm that given in input an instance of A and epsilon > 0 finds a (1 + epsilon)-approximate solution in time that is polynomial for each fixed epsilon. Typical running times are n(0(1/epsilon)) or 2(1/epsilon 0(1))n. While algorithms of the former kind tend to be impractical, the latter ones are more interesting. In several cases, the development of algorithms of the second type required considerably new, and sometimes harder, techniques. For some interesting problems, only n(0(1/epsilon)) approximation schemes are known. Under likely assumptions, we prove that for some problems (including natural ones) there cannot be approximation schemes running in time f(1/epsilon)n(0(1)), no matter how fast function f grows. Our result relies on a connection with Parameterized complexity Theory, and we show that this connection is necessary, (C) 1997 Published by Elsevier Science B.V.

关键词： computational complexity approximation algorithms parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Software refactoring at the package level using clustering techniques

引用

IET SOFTWARE 2011年第3期5卷 274-286页

作者： Alkhalid, A. Alshayeb, M. Mahmoud, A. King Abdullah Univ Sci & Technol Math & Comp Sci & Engn Div Thuwal 239556900 Saudi Arabia King Fahd Univ Petr & Minerals Dept Informat & Comp Sci Dhahran 31261 Saudi Arabia

Enhancing, modifying or adapting the software to new requirements increases the internal software complexity. Software with high level of internal complexity is difficult to maintain. Software refactoring reduces software complexity and hence decreases the maintenance effort. However, software refactoring becomes quite challenging task as the software evolves. The authors use clustering as a pattern recognition technique to assist in software refactoring activities at the package level. The approach presents a computer aided support for identifying ill-structured packages and provides suggestions for software designer to balance between intra-package cohesion and inter-package coupling. A comparative study is conducted applying three different clustering techniques on different software systems. In addition, the application of refactoring at the package level using an adaptive k-nearest neighbour (A-KNN) algorithm is introduced. The authors compared A-KNN technique with the other clustering techniques (viz. single linkage algorithm, complete linkage algorithm and weighted pair-group method using arithmetic averages). The new technique shows competitive performance with lower computational complexity.

关键词： intrapackage cohesion computer aided support software requirements software maintenance software metrics pattern recognition software design software evolution interpackage coupling software adaptation arithmetic average weighted pair-group method internal software complexity Software engineering techniques software refactoring Software metrics software modification complete linkage algorithm pattern clustering software enhancement software architecture clustering technique adaptive k-nearest neighbour algorithm single linkage algorithm computational complexity

来源：评论

学校读者我要写书评

暂无评论

Graphs that are simultaneously efficient open domination and efficient closed domination graphs

引用

DISCRETE APPLIED MATHEMATICS 2017年 217卷 613-621页

作者： Klavzar, Sandi Peterin, Iztok Yero, Ismael G. Univ Ljubljana Fac Math & Phys Ljubljana 61000 Slovenia Univ Maribor Fac Nat Sci & Math Maribor Slovenia Inst Math Phys & Mech Ljubljana Slovenia Univ Maribor Fac Elect Engn & Comp Sci Maribor Slovenia Univ Cadiz EPS Algeciras Dept Matemat Cadiz Spain

A graph is an efficient open (resp. closed) domination graph if there exists a subset of vertices whose open (resp. closed) neighborhoods partition. its vertex set. Graphs that are efficient open as well as efficient closed (shortly EOCD graphs) are investigated. The structure of EOCD graphs with respect to their efficient open and efficient closed dominating sets is explained. It is shown that the decision problem regarding whether a graph is an EOCD graph is an NP-complete problem. A recursive description, that constructs all EOCD trees is given and EOCD graphs are characterized among the Sierpinski graphs. (C) 2016 Published by Elsevier B.V.

关键词： Efficient open domination Efficient closed domination Perfect code computational complexity Tree Sierpinski graph

来源：评论

学校读者我要写书评

暂无评论

State assignment of finite-state machines

引用

IEE PROCEEDINGS-COMPUTERS AND DIGITAL TECHNIQUES 2000年第1期147卷 15-22页

作者： Ahmad, I Dhodhi, MK Kuwait Univ Dept Elect & Comp Engn Safat 13060 Kuwait

The state-assignment problem of finite-state machines (FSMs) is addressed. State assignment is a mapping from the set of states (symbolic names) of an FSM to the set of binary codes with the objective of minimising the area of the combinational circuit required to realise the FSM. It is one of the most important optimisation problems in the automatic synthesis of sequential circuits since it has a major impact on the area, speed, power and testability of the circuits. The problem of finding an optimal state assignment is NP-hard. A new scheme is presented based on mean-field annealing (MFA) to solve the graph-embedding problem which is the main step in the state-assignment process. The MFA algorithm combines the characteristics of the simulated annealing and the Hopfield neural network. To solve the problem by MFA, the graph-embedding problem is mapped into a neural network and an energy function is formulated. Experiments over the MCNC FSM benchmarks demonstrate that the proposed MFA algorithm can produce superior results compared with the specialised methods such as the MUSTANG, NOVA and genetic algorithm.

关键词： Automata theory NP-hard computational complexity finite state machines Logic and switching circuits combinational circuits MUSTANG circuit CAD state assignment Optimisation techniques Optimisation NOVA optimisation problems circuit testability computational complexity Sequential switching theory genetic algorithm automatic synthesis optimal state assignment binary codes MFA algorithm Logic circuits symbolic names Computer-aided circuit analysis and design simulated annealing mean field annealing sequential circuits Neural computing techniques Electronic engineering computing combinational circuit graph embedding problem state assignment problem Hopfield neural network MCNC FSM benchmarks energy function Hopfield neural nets

来源：评论

学校读者我要写书评

暂无评论

The complexity of error metrics

引用

INFORMATION PROCESSING LETTERS 2018年 139卷 1-7页

作者： Keszocze, Oliver Soeken, Mathias Drechsler, Rolf Univ Bremen Grp Comp Architecture Bremen Germany Ecole Polytech Fed Lausanne Integrated Syst Lab Lausanne Switzerland DFKI GmbH Cyber Phys Syst Bremen Germany

Approximate computing exploits the fact that many applications do not require the results to be exact but not to exceed a threshold in a given error metric. Algorithms in approximate computing require to compute the error of the approximation in order to measure its quality. In this paper, the computational complexity of several of such error metrics commonly used in approximate computing is investigated. We show that these metrics lie within the complexity classes FPNP and #P and, therefore, are hard to compute. We further classify the error metrics into two classes. The framework used in this generalization is then used to exemplary develop specialized error metrics. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Approximate computing computational complexity Error metrics

来源：评论

学校读者我要写书评

暂无评论

On the complexity of {k}-domination and k-tuple domination in graphs

引用

INFORMATION PROCESSING LETTERS 2015年第6-8期115卷 556-561页

作者： Argiroffo, Gabriela Leoni, Valeria Torres, Pablo Univ Nacl Rosario Dept Matemat RA-2000 Rosario Santa Fe Argentina Consejo Nacl Invest Cient & Tecn RA-1033 Buenos Aires DF Argentina

We consider two types of graph domination-{k}-domination and k-tuple domination, for a fixed positive integer k and provide new NP-complete as well as polynomial time solvable instances for their related decision problems. Regarding NP-completeness results, we solve the complexity of the {k}-domination problem on split graphs, chordal bipartite graphs and planar graphs, left open in 2008. On the other hand, by exploiting Courcelle's results on Monadic Second Order Logic, we obtain that both problems are polynomial time solvable for graphs with clique-width bounded by a constant. In addition, we give an alternative proof for the linearity of these problems on strongly chordal graphs. (C) 2015 Elsevier B.V. All rights reserved.

关键词： computational complexity {k}-Domination k-Tuple domination Split graphs Planar graphs Chordal graphs

来源：评论

学校读者我要写书评

暂无评论

Concatenated physical layer encryption scheme based on rateless codes

引用

IET COMMUNICATIONS 2018年第12期12卷 1491-1497页

作者： Huang, Ying Li, Wei Lei, Jing Natl Univ Def Technol Inst Elect Sci Cognit Commun Dept Changsha Hunan Peoples R China

A novel concatenated physical-layer encryption (CPLE) scheme is proposed in this study, where better security can be achieved as well as reliability advantage. In CPLE scheme, the encryption is embedded in rateless encoding. The secret key, which is generated from wireless channel, controls the random degree and random linear combination. The rateless codes are also concatenated with other conventional channel codes, which can achieve better reliability. Different from security codes, both the security and reliability in the proposed scheme can be improved. Furthermore, there is no extra computation requirement on decoding process. Security analysis is presented including time complexity comparison and attacks resistance in practical application. Compared to other PLE schemes, the proposed scheme achieves lower complexity, and higher channel adaptation and performance advantage. On the basis of National Institute of Standards and Technology statistical test suite, CPLE scheme can achieve randomness as the traditional cipher system such as advanced encryption standard. Furthermore, simulation results show that the CPLE scheme outperforms the conventional concatenated codes at the same coderate.

关键词： cryptography telecommunication security telecommunication network reliability wireless channels channel coding random codes decoding computational complexity statistical testing CPLE scheme rateless codes concatenated physical-layer encryption scheme secret key wireless channel random linear combination random degree control conventional channel codes reliability security codes decoding process security analysis time complexity attack resistance PLE schemes channel adaptation National Institute of Standards and Technology statistical test suite cipher system advanced encryption standard code rate

来源：评论

学校读者我要写书评

暂无评论

complexity of planning for connected agents

引用

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2020年第2期34卷 1-31页

作者： Charrier, Tristan Queffelec, Arthur Sankur, Ocan Schwarzentruber, Francois Univ Rennes Inria CNRS IRISA 263 Ave Gen Leclerc F-35000 Rennes France

We study a variant of the multi-agent path finding (MAPF) problem in which the group of agents are required to stay connected with a supervising base station throughout the execution. In addition, we consider the problem of covering an area with the same connectivity constraint. We show that both problems are PSPACE-complete on directed and undirected topological graphs while checking the existence of a bounded plan is NP-complete when the bound is given in unary (and PSPACE-hard when the encoding is in binary). Moreover, we identify a realistic class of topological graphs on which the decision problem falls in NLOGSPACE although the bounded versions remain NP-complete for unary encoding.

关键词： Artifical intelligence Multi-agent systems Planning computational complexity

来源：评论

学校读者我要写书评

暂无评论

Separation Logic with One Quantified Variable

引用

THEORY OF COMPUTING SYSTEMS 2017年第2期61卷 371-461页

作者： Demri, Stephane Galmiche, Didier Larchey-Wendling, Dominique Mery, Daniel Univ Paris Saclay CNRS ENS Paris Saclay LSV Cachan France Univ Lorraine LORIA BP 239 F-54506 Vandoeuvre Les Nancy France CNRS LORIA BP 239 F-54506 Vandoeuvre Les Nancy France

We investigate first-order separation logic with one record field restricted to a unique quantified variable (1SL1). Undecidability is known when the number of quantified variables is unbounded and the satisfiability problem is PSPACE-complete for the propositional fragment. We show that the satisfiability problem for 1SL1 is PSPACE-complete and we characterize its expressive power by showing that every formula is equivalent to a Boolean combination of atomic properties. This contributes to our understanding of fragments of first-order separation logic that can specify properties about the memory heap of programs with singly-linked lists. All the fragments we consider contain the magic wand operator and first-order quantification over a single variable.

关键词： Separation logic Quantifier elimination Model checking Satisfiability computational complexity

来源：评论

学校读者我要写书评

暂无评论

Improved algorithm for hyperspectral image classification

引用

JOURNAL OF ELECTRONIC IMAGING 2018年第6期27卷

作者： Bouzidi, Sonia Ben Braiek, Houssem Univ Tunis El Manar Inst Super Informat El Manar Lab Rech Informat Modelisat & Traitement Informat Lariana Tunisia Univ Carthage Inst Super Sci Appl & Technol Tunis Tunisia

Due to the high-dimensional data space generated by hyperspectral sensors together with the real-time requirements of several remote sensing applications, it is important to accelerate hyperspectral data analysis. For this purpose, we aim to improve the performance of an existing classification algorithm and reduce its execution time. The proposed algorithm is based on sparse representation and using extended multiattribute profiles as spectral-spatial features, and sparse unmixing by variable splitting and augmented Lagrangian as the optimization method. The speeding up is mainly achieved by exploiting the interdependencies among iterative calls and providing an appropriate memorization technique to reduce the extra cost by factorizing the algebraic computations. The experimental results on two HSI data sets prove that the optimized algorithm is really faster than the original one while retaining the same classification accuracy. This study shows how useful it is to adapt the implementation of the generic module in order to become more appropriate to the application and to minimize the extra costs as much as possible. (C) 2018 SPIE and IS&T

关键词： hyperspectral image classification computational complexity caching dynamic programming extended multiattribute profile speedup

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：