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

Optimal bit-level arithmetic optimisation for high-speed circuits

ELECTRONICS LETTERS 2000年第5期36卷 405-407页

作者： Um, J Kim, T Korea Adv Inst Sci & Technol Dept Comp Sci Taejon 305701 South Korea Korea Adv Inst Sci & Technol AITRC Taejon 305701 South Korea

In terms of speed, the Wallace-tree compressor (i.e. bit-level carry-save addition array) is widely recognised as one of the most effective schemes for implementing arithmetic computations in VLSI design. However, the scheme has been applied only in a rather restrictive way, i.e. for implementing fast multipliers and for generating fixed structures without considering the characteristic of the input signals. The authors address the problem of optimising arithmetic circuits to overcome those limitations. A polynomial time algorithm is presented which generates a delay-optimal carry-save addition structure of an arithmetic circuit with uneven signal arrival profiles. This algorithm has been applied to the optimisation of high-speed digital filters and 5-30% savings have been achieved in the overall filter implementation in comparison to the standard carry-save implementation.

关键词： arithmetic computations Wallace-tree compressor VLSI delay-optimal carry-save addition structure VLSI design Digital arithmetic methods digital arithmetic polynomial time algorithm bit-level carry-save addition array Digital filters carry logic digital filters high-speed integrated circuits uneven signal arrival profiles high-speed circuits optimal bit-level arithmetic optimisation

来源：评论

学校读者我要写书评

暂无评论

The clique-transversal set problem in claw-free graphs with degree at most 4

引用

INFORMATION PROCESSING LETTERS 2015年第2期115卷 331-335页

作者： Liang, Zuosong Shan, Erfang Qufu Normal Univ Sch Management Rizhao 276826 Peoples R China Shanghai Univ Sch Management Shanghai 200444 Peoples R China Shanghai Univ Dept Math Shanghai 200444 Peoples R China

A clique of a graph G is defined as a complete subgraph maximal under inclusion and having at least two vertices. A clique-transversal set D of G is a subset of vertices of G such that D meets all cliques of G. The clique-transversal set problem is to find a minimum clique-transversal set of G. In this paper we present a polynomial time algorithm for the clique-transversal set problem on claw-free graphs with degree at most 4. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Clique Clique-transversal set problem polynomial time algorithm Claw-free graph

来源：评论

学校读者我要写书评

暂无评论

Deadline and Buffer Constrained Knapsack Problem

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY 2019年第5期29卷 1564-1568页

作者： Elgabli, Anis Aggarwal, Vaneet Purdue Univ Sch Elect & Comp Engn W Lafayette IN 47907 USA Univ Oulu Ctr Wireless Commun Oulu 90014 Finland Purdue Univ Sch Ind Engn W Lafayette IN 47907 USA

In this paper, we formulate a problem that is a variant of the knapsack problem. Even though the problem is NP-hard in general, we consider a special case of the problem where the problem is in P. For this special case, the proposed algorithm is linear time complexity in the number of bins. The proposed framework is a generalization of the framework that has been used recently in the context of finding rate adaptation algorithms for video streaming.

关键词： Knapsack problem video streaming polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Finding Hamiltonian cycles in {quasi-claw, K_1,5, K_1,5 + e}-free graphs with bounded Dilworth numbers

引用

DISCRETE MATHEMATICS 2009年第8期309卷 2555-2558页

作者： Li, Rao Univ S Carolina Dept Math Sci Aiken SC 29801 USA

Let u and upsilon be two vertices in a graph G. We say vertex u dominates vertex upsilon if N(upsilon) subset of N(u) boolean OR {u}. If u dominates upsilon or upsilon dominates u, then u and upsilon are comparable. The Dilworth number of a graph G, denoted as Dil(G), is the largest number of pairwise incomparable vertices in the graph G. A graph G is called quasi-claw-free if it satisfies the property: d(x, y) = 2 double right arrow there exists u is an element of N(x) n N(y) such that N[u] subset of N[x] boolean OR N[y]. A graph is called {quasi-claw, K-1.5, K-1.5 + e}-free if it is quasi-claw-free and contains no induced subgraph isomorphic to K-1.5 or K-1.5 + e, where K-1.5 + e is a graph obtained by joining a pair of nonadjacent vertices in K-1.5. It is shown that if G is a k (k >= 2)-connected {quasi-claw, K-1.5, K-1.5 + e}-free graph with Dil(G) <= 2k - 1, then G is Hamiltonian and a Hamiltonian cycle in G can be found in polynomial time. (c) 2008 Elsevier B.V. All rights reserved.

关键词： Hamiltonicity Claw-free graph Quasi-claw-free graph polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

HEURISTICS FOR UNEQUAL WEIGHT DELIVERY PROBLEMS WITH A FIXED ERROR GUARANTEE

引用

OPERATIONS RESEARCH LETTERS 1987年第4期6卷 149-158页

作者： ALTINKEMER, K GAVISH, B UNIV ROCHESTER WILLIAM E SIMON GRAD SCH BUSINESS ADM ROCHESTER NY 14627 USA

This paper presents heuristics that are based on optimal partitioning of a travelling salesman tour, for solving the unequal weight delivery problem. The worst case error performance is given as a bound on the worst case ratio of the cost of the heuristic solution to the cost of the optimal solution. A fully polynomial procedure which consists of applying the optimal partitioning to a travelling salesman tour generated by Christofides' heuristic has a worst case error bound of 3.5−3/ Q where Q is the capacity limit of the vehicles. When optimal partitioning is applied to an optimal travelling salesman tour, the worst case error bound becomes 3−2/ Q .

关键词： delivery problem heuristics polynomial time algorithm travelling salesman problem worst case error bound

来源：评论

学校读者我要写书评

暂无评论

Supply chain scheduling: Sequence coordination

引用

DISCRETE APPLIED MATHEMATICS 2006年第15期154卷 2044-2063页

作者： Agnetis, Alessandro Hall, Nicholas G. Pacciarelli, Dario Univ Siena Dipartimento Ingn Informaz I-53100 Siena Italy Ohio State Univ Dept Management Sci Columbus OH 43210 USA Univ Roma Tre Dipartimento Informat & Automaz I-00146 Rome Italy

A critical issue in supply chain management is coordinating the decisions made by decision makers at different stages, for example a supplier and one or several manufacturers. We model this issue by assuming that both the supplier and each manufacturer have an ideal schedule, determined by their own costs and constraints. An interchange cost is incurred by the supplier or a manufacturer whenever the relative order of two jobs in its actual schedule is different from that in its ideal schedule. An intermediate storage buffer is available to resequence the jobs between the two stages. We consider the problems of finding an optimal supplier's schedule, an optimal manufacturer's schedule, and optimal schedules for both. The objective functions we consider are the minimization of total interchange cost, and of total interchange plus buffer storage cost. We describe efficient algorithms for all the supplier's and manufacturers' problems, as well as for a special case of the joint scheduling problem. The running time of these algorithms is polynomial in both the number of jobs and the number of manufacturers. Finally, we identify conditions under which cooperation between the supplier and a manufacturer reduces their total cost. (c) 2006 Elsevier B.V. All rights reserved.

关键词： manufacturing supply chain scheduling cooperation polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Hamilton cycles in sparse locally connected graphs

引用

DISCRETE APPLIED MATHEMATICS 2019年 257卷 276-288页

作者： van Aardt, Susan A. Burger, Alewyn P. Frick, Marietjie Thomassen, Carsten de Wet, Johan P. Univ South Africa UNISA Dept Math Sci POB 392 ZA-0003 Pretoria South Africa Univ Stellenbosch Dept Logist Private Bag X1 ZA-7602 Matieland South Africa Univ Pretoria Dept Math & Appl Math Private Bag X20 ZA-0028 Hatfield South Africa Tech Univ Denmark Dept Appl Math & Comp Sci DK-2800 Lyngby Denmark DST NRF Ctr Excellence Math & Stat Sci CoE MaSS Johannesburg South Africa

A graph G is locally connected if for every nu is an element of V(G) the open neighbourhood N(nu) of nu is nonempty and induces a connected graph in G. We characterize locally connected graphs of order n with less than 2n edges and show that for any natural number k the Hamilton Cycle Problem for locally connected graphs of order n with m edges is polynomially solvable if m <= 2n + k log(2) n, but NP-complete if m = 2n + [n(1/k)]. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Locally connected Hamiltonian NP-complete polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Completing orientations of partially oriented graphs

引用

JOURNAL OF GRAPH THEORY 2018年第3期87卷 285-304页

作者： Bang-Jensen, J. Huang, J. Zhu, X. Univ Southern Denmark Dept Math & Comp Sci DK-5230 Odense Denmark Univ Victoria Dept Math & Stat Victoria BC V8W 3R4 Canada Zhejiang Normal Univ Dept Math Jinhua Peoples R China

We initiate a general study of what we call orientation completion problems. For a fixed class C of oriented graphs, the orientation completion problem asks whether a given partially oriented graph P can be completed to an oriented graph in. by orienting the (nonoriented) edges in P. Orientation completion problems commonly generalize several existing problems including recognition of certain classes of graphs and digraphs as well as extending representations of certain geometrically representable graphs. We study orientation completion problems for various classes of oriented graphs, including k-arc-strong oriented graphs, k-strong oriented graphs, quasi-transitive-oriented graphs, local tournaments, acyclic local tournaments, locally transitive tournaments, locally transitive local tournaments, in-tournaments, and oriented graphs that have directed cycle factors. We show that the orientation completion problem for each of these classes is either polynomial time solvable or NP-complete. We also show that some of the NP-complete problems become polynomial time solvable when the input-oriented graphs satisfy certain extra conditions. Our results imply that the representation extension problems for proper interval graphs and for proper circular arc graphs are polynomial time solvable. The latter generalizes a previous result.

关键词： friendly partial oriented graph in-tournament local tournament locally transitive local tournament NP-complete orientation completion problem partially oriented graph polynomial time algorithm proper circular arc graph proper interval graph recognition representation extension

来源：评论

学校读者我要写书评

暂无评论

Finding induced trees

引用

DISCRETE APPLIED MATHEMATICS 2009年第17期157卷 3552-3557页

作者： Derhy, N. Picouleau, C. Conservatoire Natl Arts & Metiers Chaire Rech Operationnelle CEDRIC F-75003 Paris France

Let G = (V(G). E(G)) be a finite connected undirected graph and W subset of V(G) a subset of vertices. We are searching for a subset X subset of V(G) such that W subset of X and the subgraph induced on X is a tree. N P-completeness results and polynomial time algorithms are given assuming that the cardinality of W is fixed or not. Besides we give complexity results when X has to induce a path or when G is a weighted graph. We also consider problems where the cardinality of X has to be minimized. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Induced subgraph Induced tree N P-completeness polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

algorithmic aspects of upper paired-domination in graphs

引用

THEORETICAL COMPUTER SCIENCE 2020年 804卷 98-114页

作者： Henning, Michael A. Pradhan, D. Univ Johannesburg Dept Pure & Appl Math ZA-2006 Auckland Pk South Africa Indian Inst Technol ISM Dept Math & Comp Dhanbad Bihar India

A set D of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to a vertex in D and the subgraph induced by D contains a perfect matching (not necessarily as an induced subgraph). A paired-dominating set of G is minimal if no proper subset of it is a paired-dominating set of G. The upper paired-domination number of G, denoted by Gamma(pr)(G), is the maximum cardinality of a minimal paired-dominating set of G. In UPPER PDS, it is required to compute a minimal paired dominating set with cardinality Gamma(pr)(G) for a given graph G. In this paper, we show that UPPER-PDS cannot be approximated within a factor of n(1-epsilon) for any epsilon > 0, unless P=NP and UPPER-PDS is APX-complete for bipartite graphs of maximum degree 4. On the positive side, we show that UPPER PDS can be approximated within O(Delta)-factor for graphs with maximum degree Delta. We also show that UPPER-PDS is solvable in polynomial time for threshold graphs, chain graphs, and proper interval graphs. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Domination Paired-domination Upper paired-domination polynomial time algorithm NP-complete APX-complete

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：