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

32nd International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Schmid, Andreas Schmidt, Jens M. Max Planck Inst Informat Saarbrucken Germany TU Ilmenau Ilmenau Germany

ISBN: (纸本)9783939897781

A 2-walk of a graph is a walk visiting every vertex at least once and at most twice. By generalizing decompositions of Tutte and Thomassen, Gao, Richter and Yu proved that every 3-connected planar graph contains a closed 2-walk such that all vertices visited twice are contained in 3separators. This seminal result generalizes Tutte's theorem that every 4-connected planar graph is Hamiltonian as well as Barnette's theorem that every 3-connected planar graph has a spanning tree with maximum degree at most 3. The algorithmic challenge of finding such a closed 2-walk is to overcome big overlapping subgraphs in the decomposition, which are also inherent in Tutte's and Thomassen's decompositions. We solve this problem by extending the decomposition of Gao, Richter and Yu in such a way that all pieces, in which the graph is decomposed into, are edge-disjoint. This implies the first polynomial-time algorithm that computes the closed 2-walk mentioned above.

关键词： algorithms and data structures 2-walks 3-connected planar graphs Tutte paths 3-trees

来源：评论

学校读者我要写书评

暂无评论

AGGREGATED ACCOUNTING OF MEMORY USAGE IN JAVA

AGGREGATED ACCOUNTING OF MEMORY USAGE IN JAVA

引用

4th International Conference on Software and data Technologies

作者： Bouche, Paul von Loewis, Martin Troeger, Peter Nokia Siemens Networks Treptowers 1 Berlin Germany Hasso Plattner Inst Potsdam Germany Humbolt Univ Berlin Germany

ISBN: (纸本)9789896740092

Profiling of application memory consumption typically includes a trade-off between overhead and accuracy. We present a new approach for memory usage accounting which has a comparatively low overhead and still provides meaningful results. Our approach considers the structure of modern applications by introducing the notion of memory accounts where application modules get "charged" for memory allocations. We have applied this approach to Java application servers and discuss important implementation aspects as well as experimental results of our prototype.

关键词： Software engineering algorithms and data structures Software testing and maintenance

来源：评论

学校读者我要写书评

暂无评论

Boltzmann sampling of ordered structures

引用

Electronic Notes in Discrete Mathematics 2009年第C期35卷 305-310页

作者： Roussel, Olivier Soria, Michèle Équipe APR - Laboratoire d'Informatique de Paris 6 Université Pierre et Marie Curie Paris France

Boltzmann models from statistical physics, combined with methods from analytic combinatorics, give rise to efficient algorithms for the random generation of combinatorials objects. This paper proposes a Boltzmann sampler for ordered structures constructed with the box operator, which is an extension of the cartesian product. Under an abstract real-arithmetic computation model, our algorithm is of linear complexity for free generation. For generation of objects of a targetted size, provided a small tolerance, the complexity remains linear for many classes of structures. As an illustration we show how to generate alternating permutations, and our implementation makes possible to generate random objects of sizes up to 10⁷ on a standard machine. © 2009.

关键词： algorithms and data structures Analytic combinatorics Boltzmann model Random sampling Randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

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)

作者： 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

来源：评论

学校读者我要写书评

暂无评论

Improved tree decomposition based algorithms for domination-like problems 5

引用

5th Latin American Symposium on Theoretical Informatics (LATIN 2002)

作者： Alber, J Niedermeier, R Univ Tubingen Wilhelm Schickard Inst Informat D-72076 Tubingen Germany

ISBN: (纸本)3540434003

We present an improved dynamic programming strategy for DOMINATING SET and related problems on graphs that are given together with a tree decomposition of width k. We obtain an O(4(k) n) algorithm for DOMINATING SET, where n is the number of nodes of the tree decomposition. This result improves the previously best known algorithm of Telle and Proskurowski running in time O(9(k) n). The key to our result is an argument on a certain "monotonicity" in the table updating process during dynamic programming. Moreover, various other domination-like problems as discussed by Telle and Proskurowski are treated with our technique. We gain improvements on the base of the exponential term in the running time ranging between 55% and 68% in most of these cases. These results mean significant breakthroughs concerning practical implementations.

关键词： algorithms and data structures combinatorics and graph theory computational complexity

来源：评论

学校读者我要写书评

暂无评论

Satisfiability testing for boolean formulas using Δ-trees

引用

Studia Logica 2002年第1期72卷 85-112页

作者： Gutiérrez, G. De Guzmán, I.P. Martínez, J. Ojeda-Aciego, M. Valverde, A. Dept. Matemática Aplicada Universidad de Málaga 29080 Málaga P.O. Box 4114 Spain

The tree-based data structure of Δ-tree for propositional formulas is introduced in an improved and optimised form. The Δ-trees allow a compact representation for negation normal forms as well as for a number of reduction strategies in order to consider only those occurrences of literals which are relevant for the satisfiability of the input formula. These reduction strategies are divided into two subsets (meaning- and satisfiability-preserving transformations) and can be used to decrease the size of a negation normal form A at (at most) quadratic cost. The reduction strategies are aimed at decreasing the number of required branchings and, therefore, these strategies allow to limit the size of the search space for the SAT problem. © 2002 Kluwer Academic Publishers.

关键词： algorithms and data structures Automated deduction

来源：评论

学校读者我要写书评

暂无评论

LP can be a cure for Parameterized Problems

LP can be a cure for Parameterized Problems

引用

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

作者： Narayanaswamy, N. S. Raman, Venkatesh Ramanujan, M. S. Saurabh, Saket IIT Madras Dept Comp Sci & Engn Chennai Tamil Nadu India Inst Math Sci Chennai 600113 Tamil Nadu India

ISBN: (纸本)9783939897354

We investigate the parameterized complexity of VERTEX COVER parameterized above the optimum value of the linear programming (LP) relaxation of the integer linear programming formulation of the problem. By carefully analyzing the change in the LP value in the branching steps, we argue that even the most straightforward branching algorithm (after some preprocessing) results in an O*(2.6181(r)) algorithm for the problem where r is the excess of the vertex cover size over the LP optimum. We write O*(f(k)) for a time complexity of the form O(f(k)n(O(1))), where f(k) grows exponentially with k. Then, using known and new reductions, we give O*(2.6181(k)) algorithms for the parameterized versions of ABOVE GUARANTEE VERTEX COVER, ODD CYCLE TRANSVERSAL, SPLIT VERTEX DELETION AND ALMOST 2-SAT, and an O*(1.6181(k)) algorithm for KONIG VERTEX DELETION, VERTEX COVER PARAM BY OCT and VERTEX COVER PARAM BY KVD. These algorithms significantly improve the best known bounds for these problems. The notable improvement is the bound for ODD CYCLE TRANSVERSAL for which this is the first major improvement after the first algorithm that showed it fixed-parameter tractable in 2003. We also observe that using our algorithm, one can obtain a simple kernel for the classical vertex cover problem with at most 2k - O(log k) vertices.

关键词： algorithms and data structures Graph algorithms Parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Spectral Sparsification in the Semi-Streaming Setting

Spectral Sparsification in the Semi-Streaming Setting

引用

28th International Symposium on Theoretical Aspects of Computer Science (SATCS)

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

ISBN: (纸本)9783939897255

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 (O) over tilde (n) 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. In this paper, we introduce an algorithm for constructing a spectral sparsifier of G with O(n log n/epsilon(2)) edges (where epsilon is a parameter measuring the quality of the sparsifier), taking (O) over tilde (m) 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 (O) over tilde (n) 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

来源：评论

学校读者我要写书评

暂无评论

Applications Of Robust Control To Nonlinear Systems

引用

丛书名： Progress in Astronautics and Aeronautics

2004年

作者： Richard Colgren

ISBN: (数字)9781600866722

ISBN: (纸本)9781563476662

This book offers a three-step approach to generating a robust nonlinear controller: modeling, synthesis, and robustness analysis. The publication is targeted to practicing engineers and graduate-level students working in guidance, information command and control systems, and CAD/*** methods covered in this book allow the user to design and analyze nonlinear controllers for nonlinear systems with several important and unique characteristics: the ability to specify the closed loop system's frequency response via requirements on the sensitivity (S) and complementary sensitivity (T), the ability to directly minimize an undesirable resonance or peak in the frequency response while simultaneously closing all loops from the input to the output vector in essentially one single design step, and the ability to analyze the stability characteristics for multiple independent and dependent problem variables. The approach uniquely allows the user to achieve stable and robust performance for systems which are both unstable and contain discontinuous nonlinearities using adaptive nonlinear controllers.

关键词： Aerodynamics Aeronautical Engineering Aeronautics Aerospace Electronics Aerospace Engineering Aerospace Sciences Air Forces Aircraft Control Aircraft Design Aircraft Dynamic Modes Aircraft Flight Control System Aircraft Operations Aircraft Operations and Technology Aircraft Performance Aircraft Stability and Control Aircraft Wing Design Aircrafts algorithms and data structures Applied Mathematics Autonomous Systems Aviation Avionics Avionics Computers Civil Aircraft Computer Networks Computer Programming and Language Computing and Informatics Computing, Information, and Communication Control Systems Control Theory data Science Electrical Measuring Equipment Electricity Electromagnetism Elementary Algebra Feedback Control Flight Control Surfaces Flight Dynamics Flight Training Flying Qualities General Physics Guidance, Navigation, and Control Systems Inverse Problems Military Aviation Multivariable Control Nonlinear Control Theory Optimal Control Theory Optimization Algorithm Riccati Equations Search Algorithm Signal Processing

来源：评论

学校读者我要写书评

暂无评论

klcluster: Center-based Clustering of Trajectories 19

klcluster: Center-based Clustering of Trajectories

引用

27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS)

作者： Buchin, Kevin Driemel, Anne van de L'Isle, Natasja Nusser, Andre Eindhoven Tech Univ Eindhoven Netherlands Univ Bonn Hausdorff Ctr Math Bonn Germany Max Planck Inst Informat Grad Sch Comp Sci Saarbrucken Germany

ISBN: (纸本)9781450369091

Center-based clustering, in particular k-means clustering, is frequently used for point data. Its advantages include that the resulting clustering is often easy to interpret and that the cluster centers provide a compact representation of the data. Recent theoretical advances have been made in generalizing center-based clustering to trajectory data. Building upon these theoretical results, we present practical algorithms for center-based trajectory clustering.

关键词： Computational Geometry algorithms and data structures Trajectories Clustering

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：