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

Equality of domination and transversal numbers in hypergraphs

DISCRETE APPLIED MATHEMATICS 2013年第13-14期161卷 1859-1867页

作者： Arumugam, S. Jose, Bibin K. Bujtas, Csilla Tuza, Zsolt Kalasalingam Univ Natl Ctr Adv Res Discrete Math N CARDMATH Anand Nagar 626126 Krishnankoil India Univ Newcastle Sch Elect Engn & Comp Sci Callaghan NSW 2308 Australia Liverpool Hope Univ Dept Comp Sci Liverpool Merseyside England Ball State Univ Dept Comp Sci Muncie IN 47306 USA SD Coll Alappuzha PG Dept Math Aleppey 688003 Kerala India Univ Pannonia Dept Comp Sci & Syst Technol H-8200 Veszprem Hungary Hungarian Acad Sci Alfred Renyi Inst Math H-1053 Budapest Hungary

A subset S of the vertex set of a hypergraph H is called a dominating set of H if for every vertex v not in S there exists u is an element of S such that u and v are contained in an edge in H. The minimum cardinality of a dominating set in H is called the domination number of H and is denoted by gamma (H). A transversal of a hypergraph H is defined to be a subset T of the vertex set such that T boolean AND E not equal empty set for every edge E of H. The transversal number of H, denoted by tau (H), is the minimum number of vertices in a transversal. A hypergraph is of rank k if each of its edges contains at most k vertices. The inequality tau (H) >= gamma (H) is valid for every hypergraph H without isolated vertices. In this paper, we investigate the hypergraphs satisfying tau (H) = gamma (H), and prove that their recognition problem is NP-hard already on the class of linear hypergraphs of rank 3, while on unrestricted problem instances it lies inside the complexity class Theta(p)(2). Structurally we focus our attention on hypergraphs in which each subhypergraph without isolated vertices fulfills the equality tau (H') = gamma (H'). We show that if each induced subhypergraph satisfies the equality then it holds for the non-induced ones as well. Moreover, we prove that for every positive integer k, there are only a finite number of forbidden subhypergraphs of rank k, and each of them has domination number at most k. (c) 2013 Elsevier B.V. All rights reserved.

关键词： Hypergraph Domination number Transversal number Hitting set Hereditary property computational complexity Polynomial hierarchy

来源：评论

学校读者我要写书评

暂无评论

DOA and Noncircular Phase Estimation of Noncircular Signal via an Improved Noncircular Rotational Invariance Propagator Method

引用

MATHEMATICAL PROBLEMS IN ENGINEERING 2015年第1期2015卷 1-12页

作者： Chen, Xueqiang Wang, Chenghua Zhang, Xiaofei Nanjing Univ Aeronaut & Astronaut Key Lab Radar Imaging & Microwave Photon Nanjing 210016 Peoples R China Nanjing Univ Aeronaut & Astronaut Coll Elect & Informat Engn Nanjing 210016 Peoples R China

We consider the computationally efficient direction-of-arrival (DOA) and noncircular (NC) phase estimation problem of noncircular signal for uniform linear array. The key idea is to apply the noncircular propagator method (NC-PM) which does not require eigenvalue decomposition (EVD) of the covariance matrix or singular value decomposition (SVD) of the received data. Noncircular rotational invariance propagator method (NC-RI-PM) avoids spectral peak searching in PM and can obtain the closed-form solution of DOA, so it has lower computational complexity. An improved NC-RI-PM algorithm of noncircular signal for uniform linear array is proposed to estimate the elevation angles and noncircular phases with automatic pairing. We reconstruct the extended array output by combining the array output and its conjugated counterpart. Our algorithm fully uses the extended array elements in the improved propagator matrix to estimate the elevation angles and noncircular phases by utilizing the rotational invariance property between subarrays. Compared with NC-RI-PM, the proposed algorithm has better angle estimation performance and much lower computational load. The computational complexity of the proposed algorithm is analyzed. We also derive the variance of estimation error and Cramer-Rao bound (CRB) of noncircular signal for uniform linear array. Finally, simulation results are presented to demonstrate the effectiveness of our algorithm.

关键词： DIRECTION of arrival estimation (Signal processing) PHASE estimation (Electronics) SIGNAL processing SYMMETRY (Mathematics) DECOMPOSITION (Mathematics) computational complexity

来源：评论

学校读者我要写书评

暂无评论

A nonlinear lower bound for constant depth arithmetical circuits via the discrete uncertainty principle

引用

THEORETICAL COMPUTER SCIENCE 2008年第3期409卷 617-622页

作者： Jansen, Maurice J. Regan, Kenneth W. SUNY Buffalo Dept CSE Buffalo NY 14260 USA Univ Aarhus Dept Comp Sci DK-8200 Aarhus N Denmark

We prove a superlinear lower bound on the size of a bounded depth bilinear arithmetical circuit computing cyclic convolution. Our proof uses the strengthening of the Donoho-Stark uncertainty principle [D.L. Donoho, P.B. Stark, Uncertainty principles and signal recovery, SIAM journal of Applied Mathematics 49 (1989) 906-931] given by [Tao IT. Tao, An uncertainty principle for cyclic groups of prime order, Mathematical Research Letters 12 (2005) 121-127], and a combinatorial lemma by Raz and Shpilka [R. Raz, A. Shpilka, Lower bounds for matrix product, in arbitrary circuits with bounded gates, SIAM Journal of Computing 32 (2003) 488-513]. This combination and an observation on ranks of circulant matrices, which we use to give a much shorter proof of the Donoho-Stark principle, may have other applications. (C) 2008 Elsevier B.V. All rights reserved.

关键词： computational complexity Arithmetical circuits Lower bounds Constant depth bilinear circuits

来源：评论

学校读者我要写书评

暂无评论

Improved non-approximability results for minimum vertex cover with density constraints

引用

THEORETICAL COMPUTER SCIENCE 1999年第1-2期225卷 113-128页

作者： Clementi, AEF Trevisan, L Univ Roma La Sapienza Dipartimento Sci Informaz I-00198 Rome Italy Univ Geneva Ctr Informat Geneva Switzerland

We provide new non-approximability results for the restrictions of the MIN VERTEX COVER problem to bounded-degree, sparse and dense graphs. We show that for a sufficiently large B, the recent 1.16 lower bound proved by Hastad (1997) extends with negligible loss to graphs with bounded degree B. Then, we consider sparse graphs with no dense components (i.e. everywhere sparse graphs), and we show a similar result but with a better trade-off between non-approximability and sparsity, Finally, we observe that the MIN VERTEX COVER problem remains APX-complete when restricted to dense graph and thus recent techniques developed for several MAX SNP problems restricted to "dense" instances introduced by Arora et al. (1995) cannot be applied. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： computational complexity approximation algorithms vertex cover expander graphs

来源：评论

学校读者我要写书评

暂无评论

Variational Bayesian learning for background subtraction based on local fusion feature

引用

IET COMPUTER VISION 2016年第8期10卷 884-893页

作者： Yan, Junhua Wang, Shunfei Xie, Tianxia Yang, Yong Wang, Jiayi Nanjing Univ Aeronaut & Astronaut Coll Astronaut Nanjing Jiangsu Peoples R China

To resist the adverse effect of shadow interference, illumination changes, indigent texture and scenario jitter in object detection and improve performance, a background modelling method based on local fusion feature and variational Bayesian learning is proposed. First, U-LBSP (uniform-local binary similarity patterns) texture feature, lab colour and location feature are used to construct local fusion feature. U-LBSP is modified from local binary patterns in order to reduce computational complexity and better resist the influence of shadow and illumination changes. Joint colour and location feature are introduced to deal with the problem of indigent texture and scenario jitter. Then, LFGMM (Gaussian mixture model based on local fusion feature) is updated and learned by variational Bayes. In order to adapt to dynamic changing scenarios, the variational expectation maximisation algorithm is applied for distribution parameters optimisation. In this way, the optimal number of Gaussian components as well as their parameters can be automatically estimated with less time expended. Experimental results show that the authors' method achieves outstanding detection performance especially under conditions of shadow disturbances, illumination changes, indigent texture and scenario jitter. Strong robustness and high accuracy have been achieved.

关键词： image texture object detection learning (artificial intelligence) variational techniques Bayes methods expectation-maximisation algorithm computational complexity jitter image colour analysis image fusion optimisation variational Bayesian learning background subtraction shadow interference effect illumination changes indigent texture scenario jitter object detection background modelling method U-LBSP texture feature uniform-local binary similarity pattern texture feature lab colour location feature computational complexity LFGMM Gaussian mixture model based on local fusion feature variational expectation maximisation algorithm distribution parameter optimisation Gaussian components shadow disturbances

来源：评论

学校读者我要写书评

暂无评论

New computational approaches for the power dominating set problem: Set covering and the neighborhoods of zero forcing forts

引用

NETWORKS 2022年第2期79卷 202-219页

作者： Smith, Logan A. Hicks, Illya V. Rice Univ Dept Computat & Appl Math 6100 Main St MS 134 Houston TX 77005 USA

To monitor electrical activity throughout the power grid and mitigate outages, sensors known as phasor measurement units can installed. Due to implementation costs, it is desirable to minimize the number of sensors deployed while ensuring that the grid can be effectively monitored. This optimization problem motivates the graph theoretic power dominating set problem. In this paper, we propose a method for computing minimum power dominating sets via a set cover IP formulation and a novel constraint generation procedure. The set cover problem's constraints correspond to neighborhoods of zero forcing forts;we study their structural properties and show they can be separated with delayed row generation. In addition, we offer several computation enhancements which be be applied to our methodology as well as existing methods. The proposed and existing methods are evaluated in several computational experiments. In many of the larger test instances considered, the proposed method exhibits an order of magnitude runtime performance improvement.

关键词： combinatorial optimization computational complexity graph integer programming power domination zero forcing

来源：评论

学校读者我要写书评

暂无评论

On limits on the computational power of data-accumulating algorithms

引用

INFORMATION PROCESSING LETTERS 2003年第4期86卷 221-227页

作者： Bruda, SD Akl, SG Bishops Univ Dept Comp Sci Lennoxville PQ J1M 1Z7 Canada Queens Univ Sch Comp Kingston ON K7L 3N6 Canada

In the data-accumulating paradigm, inputs arrive continuously in real time, and the computation terminates when all the already received data are processed before another datum arrives. Previous research states that a constant upper bound on the running time of a successful algorithm within this paradigm exists only for particular forms of the data arrival law. This contradicts our recent conjecture that those problems that are solvable in real time are included in the class of logarithmic space-bounded computations. However, we prove that such an upper bound does exist in fact in both the parallel and sequential cases and for any polynomial arrival law, thus strengthening the mentioned conjecture. Then, we analyze an example of a noncontinuous data arrival law. We find similar properties for the sorting algorithm under such a law, namely the existence of an upper bound on the running time, suggesting that such properties do not depend on the form of the arrival law. (C) 2003 Elsevier Science B.V. All rights reserved.

关键词： computational complexity data-accumulating algorithms sorting parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

QoS-aware cell association based on traffic prediction in heterogeneous cellular networks

引用

IET COMMUNICATIONS 2017年第18期11卷 2775-2782页

作者： Qi, Yanjia Wang, Hongyu Dalian Univ Technol Sch Informat & Commun Engn Dalian 116024 Peoples R China

The mobile communication system has become increasingly complicated with the dramatic growth of user's requirement in quality of service (QoS). The high fluctuation of traffic data makes conventional cell association schemes difficult to guarantee satisfactory service in accord with traffic demand. In this study, the authors propose a novel QoS-aware cell association scheme in a heterogeneous network. Utilising traffic prediction achieved by support vector regression, the user can decide the best cell according to the future traffic demand. The authors aim at maximising the total throughput with consideration of channel gains and blocking probability in different cells and formulate the cell association as a binary combinatorial optimisation problem. Since users are selfish for their own benefits without the global information, the authors turn this problem into a game theoretical framework. To obtain the Nash equilibrium with low computation complexity, a heuristic dynamic selection algorithm is proposed by updating selection probability which enables each user to associate with the best cell independently. Numerical simulation results show that the proposed algorithm achieves a remarkable throughput gain. The number of satisfied users increases substantially under the different density of users compared with conventional cell association schemes.

关键词： cellular radio combinatorial mathematics computational complexity game theory optimisation quality of service regression analysis support vector machines telecommunication computing

来源：评论

学校读者我要写书评

暂无评论

ON UNIQUE SATISFIABILITY AND THE THRESHOLD BEHAVIOR OF RANDOMIZED REDUCTIONS

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 1995年第3期50卷 359-373页

作者： CHANG, R KADIN, J ROHATGI, P CORNELL UNIV ITHACANY 14853 UNIV MAINE ORONOME 04469

The research presented in this paper is motivated by the some new results on the complexity of the unique satisfiability problem, USAT. These results, which are shown for the first time in the paper, are: iF USAT = (P)(m) USAT, then D-P = co-D-P and PH collapses. if USAT is an element of co-D-P, then PH collapses. if USAT has OR(w), then PH collapses. The proofs of these results use only the fact that USAT is complete for D-P under randomized reductions-even though the probability bound of these reductions may be low. Furthermore, these results show that the structural complexity of USAT and of D-P many-one complete sets are very similar, and so they lend support to the argument that even sets complete under ''weak'' randomized reductions can capture the properties of the many-one complete sets. However, under these ''weak'' randomized reductions, USAT is complete for P-SAT[logn] as well, and in this case, USAT does not capture the properties of the sets many-one complete for P-SAT[logn]. To explain this anomaly, the concept of the threshold behavior of randomized reductions is developed. Tight bounds on the thresholds are shown for NP, co-NP, D-P, and co-D-P Furthermore, these results can be generalized to give upper and lower bounds on the thresholds for the Boolean hierarchy. These upper bounds are expressed in terms of Fibonacci numbers. (C) 1995 Academic Press. Inc.

关键词： computational complexity

来源：评论

学校读者我要写书评

暂无评论

An unconditional study of computational zero knowledge

引用

SIAM JOURNAL ON COMPUTING 2006年第4期36卷 1160-1214页

作者： Vadhan, Salil P. Harvard Univ Div Engn & Appl Sci Cambridge MA 02138 USA

We prove a number of general theorems about ZK, the class of problems possessing ( computational) zero-knowledge proofs. Our results are unconditional, in contrast to most previous works on ZK, which rely on the assumption that one-way functions exist. We establish several new characterizations of ZK and use these characterizations to prove results such as the following: 1. Honest-verifier ZK equals general ZK. 2. Public-coin ZK equals private-coin ZK. 3. ZK is closed under union. 4. ZK with imperfect completeness equals ZK with perfect completeness. 5. Any problem in ZK boolean AND NP can be proven in computational zero knowledge by a BPPNP prover. 6. ZK with black-box simulators equals ZK with general, non-black-box simulators. The above equalities refer to the resulting class of problems ( and do not necessarily preserve other efficiency measures such as round complexity). Our approach is to combine the conditional techniques previously used in the study of ZK with the unconditional techniques developed in the study of SZK, the class of problems possessing statistical zero-knowledge proofs. To enable this combination, we prove that every problem in ZK can be decomposed into a problem in SZK together with a set of instances from which a one-way function can be constructed.

关键词： cryptography computational complexity zero-knowledge proofs pseudoentropy language-dependent commitment schemes auxiliary-input one-way functions

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：