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

36th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Bonamy, Marthe Defrain, Oscar Heinrich, Marc Raymond, Jean-Florent Univ Bordeaux CNRS Bordeaux France Univ Clermont Auvergne LIMOS Clermont Ferrand France Univ Claude Bernard LIRIS Lyon France Tech Univ Berlin LaS Team Berlin Germany

ISBN: (纸本)9783959771009

It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this paper we prove that this is the case in triangle-free graphs. This answers a question of Kante et al. Additionally, we show that deciding if a set of vertices of a bipartite graph can be completed into a minimal dominating set is a NP-complete problem.

关键词： enumeration algorithms output-polynomial algorithms minimal dominating set triangle-free graphs split graphs

来源：评论

学校读者我要写书评

暂无评论

Solution of working space about the 4-DOF parallel mechanism by ADAMS

Solution of working space about the 4-DOF parallel mechanism...

引用

2nd International Conference on Advanced Materials Design and Mechanics (ICAMDM 2013)

作者： Zhang Ruihua Lishui Univ Lishui 323000 Zhejiang Peoples R China

ISBN: (纸本)9783037857977

This article is based on ADAMS software platform to solve working space of the 4-DOF parallel mechanism. Design a kind of 4-DOF parallel mechanism and establish virtual prototype on ADAMS software platform. Then through enumeration three branched chain parameters combination, even without the premise of kinematics positive solution, we can solve it working space using the forward solving method and get the branched chain parameter with the reference point position corresponding numerical relations. It greatly simplifies the solution of the working space of parallel mechanism, is more advantageous to parameter optimization and trajectory planning of parallel mechanism.

关键词： ADAMS 4-DOF parallel mechanism Working space enumeration algorithms Numerical algorithm Direct kinematics

来源：评论

学校读者我要写书评

暂无评论

On Maximal Chain Subgraphs and Covers of Bipartite Graphs 27th

On Maximal Chain Subgraphs and Covers of Bipartite Graphs

引用

27th International Workshop on Combinatorial algorithms (IWOCA)

作者： Calamoneri, Tiziana Gastaldello, Mattia Mary, Arnaud Sagot, Marie-France Sinaimeri, Blerina Sapienza Univ Rome Via Salaria 113 I-00198 Rome Italy INRIA Villeurbanne France Univ Lyon 1 Univ Lyon LBBE CNRS UMR558 Villeurbanne France

ISBN: (纸本)9783319445434;9783319445427

In this paper, we address three related problems. One is the enumeration of all the maximal edge induced chain subgraphs of a bipartite graph, for which we provide a polynomial delay algorithm. We give bounds on the number of maximal chain subgraphs for a bipartite graph and use them to establish the input-sensitive complexity of the enumeration problem. The second problem we treat is the one of finding the minimum number of chain subgraphs needed to cover all the edges a bipartite graph. For this we provide an exact exponential algorithm with a non trivial complexity. Finally, we approach the problem of enumerating all minimal chain subgraph covers of a bipartite graph and show that it can be solved in quasi-polynomial time.

关键词： Chain subgraph cover problem enumeration algorithms Exact exponential algorithms

来源：评论

学校读者我要写书评

暂无评论

On Software Simulation of Linearisation Attacks on FCSR-based Stream Ciphers

On Software Simulation of Linearisation Attacks on FCSR-base...

引用

10th International Bhurban Conference on Applied Science and Technology (IBCAST)

作者： Ali, Arshad CESAT Islamabad Pakistan

ISBN: (纸本)9781467344265;9781467344258

Feedback with Carry Shift Registers (FCSRs) are being explored for their usage as building blocks in stream ciphers. Linearisation attacks are most effective attacks on a class of FCSR-based stream ciphers, which use filtered Galois FCSRs as building blocks. This paper presents techniques for software simulation of these attacks on such ciphers. In order to describe these techniques, the paper uses a small scale variant of the F-FCSR-H v2 type keystream generators, which is known as T-cipher. The paper uses the pseudorandom keystream generator of the T-cipher to develop a statistical analysis. The paper uses this analysis to demonstrate various aspects of the implementation of linearisation attacks on such ciphers. Moreover the paper presents a pseudocode algorithm along with its implementation details for computing the success characteristics of linearisation attacks. The paper also presents enumeration and pseudocode algorithms for solving systems of polynomial equations in the finite field F-2.

关键词： Linearisation Attacks F-FCSR-H v2 Statistical Analysis T-cipher enumeration algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficiently mining rich subgraphs from vertex-attributed graphs 20

Efficiently mining rich subgraphs from vertex-attributed gra...

引用

11th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics (ACM-BCB)

作者： Hakim, Riyad Salem, Saeed North Dakota State Univ Dept Comp Sci Fargo ND 58105 USA

ISBN: (纸本)9781450379649

With the rapid collection of large network data such as biological networks and social networks, it has become very important to develop efficient techniques for network analysis. In many domains, additional attribute data can be associated with entities and relationships in the network, where the network data represents relationships among entities in the network and the attribute data represents various characteristics of the corresponding entities and relationships in the network. Simultaneous analysis of both network and attribute data results in detection of subnetworks that are contextually meaningful. We propose an efficient algorithm for enumerating all connected vertex sets in an undirected graph. Extending this enumeration approach, an algorithm for enumerating all maximal cohesive connected vertex sets in a vertex-attributed graph is proposed. To prune search branches that will not yield maximal patterns, we also present three pruning techniques for efficient enumeration of the maximal cohesive connected vertex sets. Our comparative runtime analyses show the efficiency and effectiveness of our proposed approaches. Gene set enrichment analysis shows that protein-protein interaction subnetworks with similar cancer dysregulation attributes are biologically significant.

关键词： Cohesive connected subgraphs attributed graphs enumeration algorithms

来源：评论

学校读者我要写书评

暂无评论

Some Problems Related to the Space of Optimal Tree Reconciliations (Invited Talk) 16th

Some Problems Related to the Space of Optimal Tree Reconcili...

引用

16th International Conference and Workshops on algorithms and Computation

作者： Calamoneri, Tiziana Sinaimeri, Blerina Sapienza Univ Rome Rome Italy LUISS Univ Rome Italy INRIA Grenoble Rhone Alpes Erable Montbonnot St Martin France

ISBN: (纸本)9783030967307;9783030967314

Tree reconciliation is a general framework for investigating the evolution of strongly dependent systems as hosts and parasites or genes and species, based on their phylogenetic information. Indeed, informally speaking, it reconciles any differences between two phylogenetic trees by means of biological events. Tree reconciliation is usually computed according to the parsimony principle, that is, to each evolutionary event a cost is assigned and the goal is to find tree reconciliations of minimum total cost. Unfortunately, the number of optimal reconciliations is usually huge and many biological applications require to enumerate and to examine all of them, so it is necessary to handle them. In this paper we list some problems connected with the management of such a big space of tree reconciliations and, for each of them, discuss some known solutions.

关键词： Tree Reconciliation enumeration algorithms Visualization algorithms Clustering

来源：评论

学校读者我要写书评

暂无评论

Cold Boot Attacks on Bliss 6th

Cold Boot Attacks on Bliss

引用

6th International Conference on Cryptology and Information Security in Latin America (LATINCRYPT)

作者： Villanueva-Polanco, Ricardo Univ Norte Barranquilla Colombia

ISBN: (纸本)9783030305307;9783030305291

In this paper, we examine the feasibility of cold boot attacks against the BLISS signature scheme. We believe this to be the first time that this has been attempted. Our work is the continuation of the trend to develop cold boot attacks for different schemes as revealed by the literature. But it is also the continuation of the evaluation of post-quantum cryptographic schemes against this class of attack. Particularly, we review the BLISS implementation provided by the strongSwan project. This implementation particularly stores its private key in memory in an interesting way therefore requiring novel approaches to key recovery. We present various approaches to key recovery. We first analyse the key recovery problem in this particular case via key enumeration algorithms, and so propose different techniques for key recovery. We then turn our attention to exploit further the algebraic relation among the components of the private key, and we thus establish a connection between the key recovery problem in this particular case and an instance of Learning with Errors Problem (LWE). We then explore various key recovery techniques to tackle this instance of LWE. In particular, we show a key recovery strategy combining lattice techniques and key enumeration. Finally, we report results from experimenting with one of the key recovery algorithms for a range of parameters, showing it is able to tolerate a noise level of alpha = 0.001 and beta = 0.09 for a parameter set when performing a 2(40) enumeration.

关键词： Cold boot attacks enumeration algorithms Noisy image Key recovery Learning with Errors Problem

来源：评论

学校读者我要写书评

暂无评论

Isolation concepts applied to temporal clique enumeration

引用

NETWORK SCIENCE 2021年第Sup1期9卷 S83-S105页

作者： Molter, Hendrik Niedermeier, Rolf Renken, Malte TU Berlin Fac 4 Algorithm & Computat Complex Berlin Germany

Isolation is a concept originally conceived in the context of clique enumeration in static networks, mostly used to model communities that do not have much contact to the outside world. Herein, a clique is considered isolated if it has few edges connecting it to the rest of the graph. Motivated by recent work on enumerating cliques in temporal networks, we transform the isolation concept to the temporal setting. We discover that the addition of the time dimension leads to six distinct natural isolation concepts. Our main contribution is the development of parameterized enumeration algorithms for five of these six isolation types for clique enumeration, employing the parameter "degree of isolation." In a nutshell, this means that the more isolated these cliques are, the faster we can find them. On the empirical side, we implemented and tested these algorithms on (temporal) social network data, obtaining encouraging results.

关键词： community detection dense subgraphs social network analysis time-evolving data enumeration algorithms fixed-parameter tractability

来源：评论

学校读者我要写书评

暂无评论

Discovery and implementation of a novel pathway for n-butanol production via 2-oxoglutarate

引用

BIOTECHNOLOGY FOR BIOFUELS 2019年第1期12卷 230-230页

作者： Ferreira, Sofia Pereira, Rui Liu, Filipe Vilaca, Paulo Rocha, Isabel Univ Minho CEB Ctr Biol Engn Campus Gualtar P-4710057 Braga Portugal SilicoLife Lda Rua Canastreiro 15 P-4715387 Braga Portugal Chalmers Univ Technol Dept Biol & Biol Engn S-41296 Gothenburg Sweden Argonne Natl Lab Math & Comp Sci Div 9700 S Cass Ave Argonne IL 60439 USA Univ Nova Lisboa ITQB NOVA Inst Tecnol Quim & Biol Antonio Xavier Oeiras Portugal

Background One of the European Union directives indicates that 10% of all fuels must be bio-synthesized by 2020. In this regard, biobutanol-natively produced by clostridial strains-poses as a promising alternative biofuel. One possible approach to overcome the difficulties of the industrial exploration of the native producers is the expression of more suitable pathways in robust microorganisms such as Escherichia coli. The enumeration of novel pathways is a powerful tool, allowing to identify non-obvious combinations of enzymes to produce a target compound. Results This work describes the in silico driven design of E. coli strains able to produce butanol via 2-oxoglutarate by a novel pathway. This butanol pathway was generated by a hypergraph algorithm and selected from an initial set of 105,954 different routes by successively applying different filters, such as stoichiometric feasibility, size and novelty. The implementation of this pathway involved seven catalytic steps and required the insertion of nine heterologous genes from various sources in E. coli distributed in three plasmids. Expressing butanol genes in E. coli K12 and cultivation in High-Density Medium formulation seem to favor butanol accumulation via the 2-oxoglutarate pathway. The maximum butanol titer obtained was 85 +/- 1 mg L-1 by cultivating the cells in bioreactors. Conclusions In this work, we were able to successfully translate the computational analysis into in vivo applications, designing novel strains of E. coli able to produce n-butanol via an innovative pathway. Our results demonstrate that enumeration algorithms can broad the spectrum of butanol producing pathways. This validation encourages further research to other target compounds.

关键词： n-Butanol E coli Metabolic engineering enumeration algorithms 2-Oxoglutarate

来源：评论

学校读者我要写书评

暂无评论

On the preferred extensions of argumentation frameworks: Bijections with naive sets

引用

INFORMATION PROCESSING LETTERS 2023年 181卷

作者： Elaroussi, Mohammed Nourine, Lhouari Radjef, Mohammed Said Vilmin, Simon Univ Bejaia Fac Sci Exactes Un Rech LaMOS Bejaia 06000 Algeria Univ Clermont Auvergne CNRS Mines St Etienne LIMOSClermont Auvergne INP F-63000 Clermont Ferrand France Univ Lyon 2 Univ Lyon INSA Lyon CNRSLIRISUMR5205UCBLCent Lyon F-69621 Villeurbanne France

This paper deals with the problem of finding the preferred extensions of an argumentation framework by means of a bijection with the naive sets of another framework. First, we consider the case where an argumentation framework is naive-bijective: its naive sets and preferred extensions are equal. Recognizing naive-bijective argumentation frameworks is hard, but we show that it is tractable for frameworks with bounded in-degree. Next, we give a bijection between the preferred extensions of an argumentation framework being admissible-closed (the intersection of two admissible sets is admissible) and the naive sets of another framework on the same set of arguments. On the other hand, we prove that identifying admissible-closed argumentation frameworks is coNP-complete. At last, we introduce the notion of irreducible self-defending sets as those that are not the union of others. It turns out there exists a bijection between the preferred extensions of an argumentation framework and the naive sets of a framework on its irreducible self-defending sets. Consequently, the preferred extensions of argumentation frameworks with some lattice properties can be listed with polynomial delay and polynomial space. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Combinatorial problems Computational complexity enumeration algorithms Argumentation frameworks Preferred extensions

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：