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

Beyond Max-Cut: λ-extendible properties parameterized above the Poljak-Turzik bound

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2014年第7期80卷 1384-1403页

作者： Mnich, Matthias Philip, Geevarghese Saurabh, Saket Suchy, Ondrej Max Planck Inst Informat D-66123 Saarbrucken Germany Inst Math Sci Chennai 600113 Tamil Nadu India Czech Tech Univ CR-16635 Prague Czech Republic

We define strong lambda-extendibility as a variant of the notion of lambda-extendible properties of graphs (Poljak and Turzik, Discrete Mathematics, 1986). We show that the parameterized APT(Pi) problem - given a connected graph G on n vertices and m edges and an integer parameter k, does there exist a spanning subgraph H of G such that H is an element of Pi and H has at least [GRAPHICS] edges - is fixed-parameter tractable (FPT) for all 0 < lambda < 1, for all strongly lambda-extendible graph properties Pi for which the APT(Pi) problem is FPT on graphs which are 0(k) vertices away from being a graph in which each block is a clique. Our results hold for properties of oriented graphs and graphs with edge labels, generalize the recent result of Crowston et al. (ICALP 2012) on MAX-CUT parameterized above the Edwards-Erdos bound, and yield FPT algorithms for several graph problems parameterized above lower bounds. (C) 2014 Elsevier Inc. All rights reserved.

关键词： algorithms and data structures Fixed-parameter tractable algorithms Above-guarantee parameterization MAX-CUT lambda-extendible properties

来源：评论

学校读者我要写书评

暂无评论

Parameterized Complexity of Induced Graph Matching on Claw-Free Graphs

引用

ALGORITHMICA 2014年第3期70卷 513-560页

作者： Hermelin, Danny Mnich, Matthias van Leeuwen, Erik Jan Ben Gurion Univ Negev IL-84105 Beer Sheva Israel Cluster Excellence MMCI D-66123 Saarbrucken Germany Max Planck Inst Informat D-66123 Saarbrucken Germany

The Induced Graph Matching problem asks to find disjoint induced subgraphs isomorphic to a given graph in a given graph such that there are no edges between vertices of different subgraphs. This problem generalizes the classical Independent Set and Induced Matching problems, among several other problems. We show that Induced Graph Matching is fixed-parameter tractable in on claw-free graphs when is a fixed connected graph, and even admits a polynomial kernel when is a complete graph. Both results rely on a new, strong, and generic algorithmic structure theorem for claw-free graphs. Complementing the above positive results, we prove -hardness of Induced Graph Matching on graphs excluding as an induced subgraph, for any fixed complete graph . In particular, we show that Independent Set is -hard on -free graphs. Finally, we consider the complexity of Induced Graph Matching on a large subclass of claw-free graphs, namely on proper circular-arc graphs. We show that the problem is either polynomial-time solvable or -complete, depending on the connectivity of and the structure of G.

关键词： algorithms and data structures Induced matchings Claw-free graphs Fixed-parameter tractability

来源：评论

学校读者我要写书评

暂无评论

Parameterized Complexity of Induced Graph Matching on Claw-Free Graphs

Parameterized Complexity of Induced Graph Matching on Claw-F...

引用

20th Annual European Symposium on algorithms (ESA)

关键词： algorithms and data structures Induced matchings Claw-free graphs Fixed-parameter tractability

来源：评论

学校读者我要写书评

暂无评论

Computational Intelligence in Aerospace Sciences

引用

丛书名： Progress in Astronautics and Aeronautics

2014年

作者： Massimiliano Vasile Victor M. Becerra

ISBN: (数字)9781624102714

ISBN: (纸本)9781624102608

In the aerospace sciences, computational intelligence techniques are now key tools in addressing many problems. Such techniques have progressed along with increases in computing power, allowing numerical simulation to gradually replace experimental testing in many areas of engineering, and leading to an increasing use of nature-inspired numerical optimization methods to handle complex real world multidisciplinary design *** Intelligence in Aerospace Sciences introduces the fundamental concepts and methods used in single and multiobjective optimization, game theory, and uncertainty quantification before detailing techniques across four main areas: It provides practitioners with an overview of different computational intelligence techniques with aerospace applications, and aids newcomers to this field of research who are looking for fundamental information with advanced examples.

关键词： Aeroacoustics Aerodynamic Performance Aerodynamics Aeronautical Engineering Aeronautics Aerospace Engineering Aerospace Sciences Aircraft Components and Structure Aircraft Conceptual Design Aircraft Design Aircraft Operations Aircraft Operations and Technology Aircraft Stability and Control Aircraft Wing Design Aircrafts Airfoil algorithms and data structures Applied Mathematics Artificial Intelligence Artificial Neural Network Asteroids Astrodynamics Astronautics Astronomical Events Astronomy Autonomous Systems Avionics Computers Beam (structures) Boundary Element Method Boundary Layers Celestial Coordinate System Celestial Mechanics Communication System Computational Fluid Dynamics Computer Graphics Computer Networks Computer Programming and Language Computer Storage Devices Computer Vision Computing System Computing and Informatics Computing, Information, and Communication Conservation of Momentum Equations Control Theory data Science Dwarf Planets Equations of Fluid Dynamics European Space Agency Evolutionary Algorithm Finite Element Method Finite Element Software Flexible and Active structures Flight Control Surfaces Flight Recorder Flow Regimes Fluid Dynamics Fluid Flow Properties Fluid Mechanics General Physics Genetic Algorithm Guidance, Navigation, and Control Systems Human-Computer Interaction Human-Machine Interaction Human-Robot Interaction Interplanetary Spaceflight Kalman Filter Kepler's Laws of Planetary Motion Machine Learning Manipulators Marine Navigation Mathematical Analysis Mesh Generation Monte Carlo Method Moons of Jupiter Moons of Saturn Navigational Guidance Numerical Analysis Numerical Interpolation Oblique Shock Wave Optimization Algorithm Orbital Maneuvers Orbital Property Planetary Rovers Planetary Science and Exploration Planets Pseudospectral Methods Robot Control Robot Kinematics Robotic Sensing Robotics Robots SONAR Search Algorithm Shock Waves Signal Processing Solar Physics Solar System Moons Space Agencies Space Exploration and Technology Space Missions Space Orbit Space Robot

来源：评论

学校读者我要写书评

暂无评论

Factoring Sparse Bivariate Polynomials Using the Priority Queue

Factoring Sparse Bivariate Polynomials Using the Priority Qu...

引用

16th International Workshop on Computer Algebra in Scientific Computing (CASC)

作者： Abu Salem, Fatima K. El-Harake, Khalil Gemayel, Karl Amer Univ Beirut Dept Comp Sci Beirut Lebanon Georgia Inst Technol Sch Computat Sci & Engn Atlanta GA USA

ISBN: (纸本)9783319105154

We revisit the polytope method for factoring sparse bivariate polynomials over finite fields, and address the bottleneck arising from solving the Hensel lifting equations using the sparse distributed polynomial representation. We revise the analysis when polynomials are represented as such, which reveals how performing the polynomial multiplications and ensuing additions in separate (serialised) phases causes the Hensel lifting phase to suffer from poor work, space, and I/O complexity, and hinges on the size of the intermediary output, as size is defined in the sparse distributed representation. We propose to overlap all polynomial arithmetic in one Hensel lifting step using a MAX priority queue. The overlapping approach adapts not only to the growth in the degree of the input polynomial but also to irregularities in the sparsity of intermediary output. It also results in evading expression swell and reducing the overall work and space complexity by an order of magnitude. When the priority queue is implemented as a cache-oblivious data structure, the overlapping approach achieves an order of magnitude improvement in I/O over the serialised approach, even when the latter is using cache efficient structures to assist in polynomial multiplications and additions. We present empirical results for the polytope method using a max-heap implementation of the global priority queue, which demonstrate extremely superior performance, and specifically against Magma, for sufficiently sparse input polynomials of very high degrees.

关键词： algorithms and data structures Performance evaluation data Locality Bivariate Polynomial Factorisation Hensel Lifting Newton Polytope

来源：评论

学校读者我要写书评

暂无评论

Optimal eviction policies for stochastic address traces

引用

THEORETICAL COMPUTER SCIENCE 2013年 514卷 36-60页

作者： Bilardi, Gianfranco Versaci, Francesco Univ Padua Dept Informat Engn I-35100 Padua Italy

The eviction problem for memory hierarchies is studied for the Hidden Markov Reference Model (HMRM) of the memory trace, showing how miss minimization can be naturally formulated in the optimal control setting. In addition to the traditional version assuming a buffer of fixed capacity, a relaxed version is also considered, in which buffer occupancy can vary and its average is constrained. Resorting to multiobjective optimization, viewing occupancy as a cost rather than as a constraint, the optimal eviction policy is obtained by composing solutions for the individual addressable items. This approach is then specialized to the Least Recently Used Stack Model (LRUSM), a type of HMRM often considered for traces, which includes V - 1 parameters, where V is the size of the virtual space. A gain optimal policy for any target average occupancy is obtained which (i) is computable in time O(V) from the model parameters, (ii) is optimal also for the Fixed capacity case, and (iii) is characterized in terms of priorities, with the name of Least Profit Rate (LPR) policy. An O(log C) upper bound (being C the buffer capacity) is derived for the ratio between the expected miss rate of LPR and that of OPT, the optimal off-line policy;the upper bound is tightened to O(1), under reasonable constraints on the LRUSM parameters. Using the stack-distance framework, an algorithm is developed to compute the number of misses incurred by LPR on a given input trace, simultaneously for all buffer capacities, in time O(log V) per access. Finally, some results are provided for miss minimization over a finite horizon and over an infinite horizon under bias optimality, a criterion more stringent than gain optimality. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Eviction policies Paging Online problems algorithms and data structures Markov chains Optimal control Multiobjective optimization

来源：评论

学校读者我要写书评

暂无评论

Spectral Sparsification in the Semi-streaming Setting

引用

THEORY OF COMPUTING SYSTEMS 2013年第2期53卷 243-262页

作者： Kelner, Jonathan A. Levin, Alex MIT Dept Math Cambridge MA 02139 USA

Let G be a graph with n vertices and m edges. A sparsifier of G is a sparse graph on the same vertex set approximating G in some natural way. It allows us to say useful things about G while considering much fewer than m edges. The strongest commonly-used notion of sparsification is spectral sparsification;H is a spectral sparsifier of G if the quadratic forms induced by the Laplacians of G and H approximate one another well. This notion is strictly stronger than the earlier concept of combinatorial sparsification. In this paper, we consider a semi-streaming setting, where we have only storage space, and we thus cannot keep all of G. In this case, maintaining a sparsifier instead gives us a useful approximation to G, allowing us to answer certain questions about the original graph without storing all of it. We introduce an algorithm for constructing a spectral sparsifier of G with O(nlogn/I mu (2)) edges (where I mu is a parameter measuring the quality of the sparsifier), taking time and requiring only one pass over G. In addition, our algorithm has the property that it maintains at all times a valid sparsifier for the subgraph of G that we have received. Our algorithm is natural and conceptually simple. As we read edges of G, we add them to the sparsifier H. Whenever H gets too big, we resparsify it in time. Adding edges to a graph changes the structure of its sparsifier's restriction to the already existing edges. It would thus seem that the above procedure would cause errors to compound each time that we resparsify, and that we should need to either retain significantly more information or reexamine previously discarded edges in order to construct the new sparsifier. However, we show how to use the information contained in H to perform this resparsification using only the edges retained by earlier steps in nearly linear time.

关键词： algorithms and data structures Graph algorithms Spectral graph theory Sub-linear space algorithms Spectral sparsification

来源：评论

学校读者我要写书评

暂无评论

Lower Bounds on Performance of Metric Tree Indexing Schemes for Exact Similarity Search in High Dimensions

引用

ALGORITHMICA 2013年第2期66卷 310-328页

作者： Pestov, Vladimir Univ Ottawa Dept Math & Stat Ottawa ON K1N 6N5 Canada

Within a mathematically rigorous model, we analyse the curse of dimensionality for deterministic exact similarity search in the context of popular indexing schemes: metric trees. The datasets X are sampled randomly from a domain Omega, equipped with a distance, rho, and an underlying probability distribution, mu. While performing an asymptotic analysis, we send the intrinsic dimension d of Omega to infinity, and assume that the size of a dataset, n, grows superpolynomially yet subexponentially in d. Exact similarity search refers to finding the nearest neighbour in the dataset X to a query point omega a Omega, where the query points are subject to the same probability distribution mu as datapoints. Let denote a class of all 1-Lipschitz functions on Omega that can be used as decision functions in constructing a hierarchical metric tree indexing scheme. Suppose the VC dimension of the class of all sets {omega:f(omega)a parts per thousand yena}, aaa"e is o(n (1/4)/log(2) n). (In view of a 1995 result of Goldberg and Jerrum, even a stronger complexity assumption d (O(1)) is reasonable.) We deduce the Omega(n (1/4)) lower bound on the expected average case performance of hierarchical metric-tree based indexing schemes for exact similarity search in (Omega,X). In paricular, this bound is superpolynomial in d.

关键词： algorithms and data structures Indexing schemes Similarity search Vapnik-Chernonenkis theory Algorithm performance

来源：评论

学校读者我要写书评

暂无评论

Feedback Vertex Sets in Tournaments

引用

JOURNAL OF GRAPH THEORY 2013年第1期72卷 72-89页

作者： Gaspers, Serge Mnich, Matthias Vienna Univ Technol Inst Informat Syst A-1040 Vienna Austria Tech Univ Eindhoven NL-5600 MB Eindhoven Netherlands

We study combinatorial and algorithmic questions around minimal feedback vertex sets (FVS) in tournament graphs. On the combinatorial side, we derive upper and lower bounds on the maximum number of minimal FVSs in an n-vertex tournament. We prove that every tournament on n vertices has at most 1.6740n minimal FVSs, and that there is an infinite family of tournaments, all having at least 1.5448n minimal FVSs. This improves and extends the bounds of Moon (1971). On the algorithmic side, we design the first polynomial space algorithm that enumerates the minimal FVSs of a tournament with polynomial delay. The combination of our results yields the fastest known algorithm for finding a minimum-sized FVS in a tournament.

关键词： algorithms and data structures tournaments feedback vertex set polynomial delay combinatorial bounds

来源：评论

学校读者我要写书评

暂无评论

Construction Sequences and Certifying 3-connectivity

引用

ALGORITHMICA 2012年第1-2期62卷 192-208页

作者： Schmidt, Jens M. Free Univ Berlin Dept Comp Sci Berlin Germany

Tutte proved that every 3-vertex-connected graph G on more than 4 vertices has a contractible edge. Barnette and Grunbaum proved the existence of a removable edge in the same setting. We show that the sequence of contractions and the sequence of removals from G to K (4) can be computed in O(|V|(2)) time by extending Barnette's and Grunbaum's theorem. As an application, we derive a certificate for the 3-vertex-connectivity of graphs that can be easily computed and verified.

关键词： algorithms and data structures Construction sequence 3-connected Certifying algorithm Tutte contraction Removable edges

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：