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

A strengthened analysis of an algorithm for DOMINATING SET in planar graphs

DISCRETE APPLIED MATHEMATICS 2012年第6期160卷 793-798页

作者： Hagerup, Torben Univ Augsburg Inst Informat D-86135 Augsburg Germany

Alber et al. presented an algorithm for computing a dominating set of size at most k, if one exists, in an undirected planar n-vertex graph and bounded its execution time by O(8(k)0). Here it is shown that the algorithm performs better than claimed by its authors. More significantly, if k <= n/19, even a much simplified version of the algorithm runs in O(7(k)n) time. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Dominating set Planar graph parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2012年第1期78卷 151-163页

作者： Gutin, Gregory van Iersel, Leo Mnich, Matthias Yeo, Anders Univ London Egham TW20 0EX Surrey England Univ Canterbury Christchurch 1 New Zealand Tech Univ Eindhoven NL-5600 MB Eindhoven Netherlands

A ternary Permutation-CSP is specified by a subset Pi of the symmetric group S-3. An instance of such a problem consists of a set of variables V and a multiset of constraints, which are ordered triples of distinct variables of V. The objective is to find a linear ordering alpha of V that maximizes the number of triples whose rearrangement (under alpha) follows a permutation in Pi. We prove that every ternary Permutation-CSP parameterized above average has a kernel with a quadratic number of variables. (C) 2011 Elsevier Inc. All rights reserved.

关键词： Constraint satisfaction Permutation parameterized complexity Kernels Probabilistic method

来源：评论

学校读者我要写书评

暂无评论

parameterized Modal Satisfiability

引用

ALGORITHMICA 2012年第1期64卷 38-55页

作者： Achilleos, Antonis Lampis, Michael Mitsou, Valia CUNY Dept Comp Sci Grad Ctr New York NY 10016 USA

We investigate the parameterized computational complexity of the satisfiability problem for modal logic and attempt to pinpoint relevant structural parameters which cause the problem's combinatorial explosion, beyond the number of propositional variables v. To this end we study the modality depth, a natural measure which has appeared in the literature, and show that, even though modal satisfiability parameterized by v and the modality depth is FPT, the running time's dependence on the parameters is a tower of exponentials (unless P = NP). To overcome this limitation we propose possible alternative parameters, namely diamond dimension and modal width. We show fixed-parameter tractability results using these measures where the exponential dependence on the parameters is much milder (doubly and singly exponential respectively) than in the case of modality depth thus leading to FPT algorithms for modal satisfiability with much more reasonable running times. We also give lower bound arguments which prove that our algorithms cannot be improved significantly unless the Exponential Time Hypothesis fails.

关键词： Modal logic parameterized complexity Satisfiability problems

来源：评论

学校读者我要写书评

暂无评论

On bounded block decomposition problems for under-specified systems of equations

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2012年第1期78卷 336-347页

作者： Bomhoff, Matthijs Kern, Walter Still, Georg Univ Twente Fac Elect Engn Math & Comp Sci NL-7500 AE Enschede Netherlands

When solving a system of equations, it can be beneficial not to solve it in its entirety at once, but rather to decompose it into smaller subsystems that can be solved in order. Based on a bisimplicial graph representation we analyze the parameterized complexity of two problems central to such a decomposition: The FREE SQUARE BLOCK problem related to finding smallest subsystems that can be solved separately, and the BOUNDED BLOCK DECOMPOSITION problem related to determining a decomposition where the largest subsystem is as small as possible. We show both problems to be W[1]-hard. Finally we relate these problems to crown structures and settle two open questions regarding them using our results. (C) 2011 Elsevier Inc. All rights reserved.

关键词： Bipartite graphs Decomposition parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Well Quasi Orders in Subclasses of Bounded Treewidth Graphs and Their Algorithmic Applications

引用

ALGORITHMICA 2012年第1期64卷 3-18页

作者： Fellows, Michael R. Hermelin, Danny Rosamond, Frances A. Max Plank Inst Informat D-66123 Saarbrucken Germany Charles Darwin Univ Sch Engn & Informat Technol Darwin NT 0909 Australia

We show that three subclasses of bounded treewidth graphs are well quasi ordered by refinements of the minor order. Specifically, we prove that graphs with bounded vertex cover are well quasi ordered by the induced subgraph order, graphs with bounded feedback vertex set are well quasi ordered by the topological-minor order, and graphs with bounded circumference are well quasi ordered by the induced minor order. Our results give algorithms for recognizing any graph family in these classes which is closed under the corresponding minor order refinement.

关键词： Well quasi order Treewidth Tree decomposition Bounded vertex cover graphs Bounded feedback vertex set graphs Bounded circumference graphs parameterized complexity Exact algorithms Meta-algorithms Geometric graph recognition String graphs

来源：评论

学校读者我要写书评

暂无评论

Catalan structures and dynamic programming in H-minor-free graphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2012年第5期78卷 1606-1622页

作者： Dorn, Frederic Fomin, Fedor V. Thilikos, Dimitrios M. SINTEF Energy Res Trondheim Norway Univ Bergen Dept Informat N-5008 Bergen Norway Univ Athens Dept Math Athens Greece

We give an algorithm that, for a fixed graph H and integer k, decides whether an n-vertex H-minor-free graph G contains a path of length k in 2(O(root k)) . n(O(1)) steps. Our approach builds on a combination of Demaine-Hajiaghayi's bounds on the size of an excluded grid in such graphs with a novel combinatorial result on certain branch decompositions of H-minor-free graphs. This result is used to bound the number of ways vertex disjoint paths can be routed through the separators of such decompositions. The proof is based on several structural theorems from the Graph Minors series of Robertson and Seymour. With a slight modification, similar combinatorial and algorithmic results can be derived for many other problems. Our approach can be viewed as a general framework for obtaining time 2(O(root k)) . n(O(1)) algorithms on H-minor-free graph classes. (C) 2012 Elsevier Inc. All rights reserved.

关键词： parameterized complexity Longest path Minor-free graphs Catalan structure

来源：评论

学校读者我要写书评

暂无评论

Multicut in trees viewed through the eyes of vertex cover

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2012年第5期78卷 1637-1650页

作者： Chen, Jianer Fan, Jia-Hao Kanj, Iyad Liu, Yang Zhang, Fenghui DePaul Univ Chicago IL 60604 USA Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA Univ Texas Pan Amer Dept Comp Sci Edinburg TX 78539 USA Google Kirkland Kirkland WA 98033 USA

We take a new look at the multicut problem in trees, denoted MULTICUT ON TREES henceforth, through the eyes of the VERTEX COVER problem. This connection, together with other techniques that we develop, allows us to give an upper bound of O(k(3)) on the kernel size for MULTICUT ON TREES, significantly improving the O(k(6)) upper bound given by Bousquet et al. We exploit this connection further to present a parameterized algorithm for MULTICUT ON TREES that runs in time O*(rho(k)), where rho = (root 5 + 1)/2 approximate to 1.618. This improves the previous (time) upper bound of O*(2(k)), given by Guo and Niedermeier, for the problem. (C) 2012 Elsevier Inc. All rights reserved.

关键词： parameterized complexity Kernelization parameterized algorithms Multicut

来源：评论

学校读者我要写书评

暂无评论

A strengthened analysis of an algorithm for DOMINATING SET in planar graphs

A strengthened analysis of an algorithm for DOMINATING SET i...

引用

4th Workshop on Graph Classes, Optimization, and Width Parameters (GROW)

作者： Hagerup, Torben Univ Augsburg Inst Informat D-86135 Augsburg Germany

关键词： Dominating set Planar graph parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Representative sets and irrelevant vertices: New tools for kernelization

Representative sets and irrelevant vertices: New tools for k...

引用

IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS)

作者： Kratsch, Stefan Wahlstroem, Magnus Univ Utrecht Utrecht Netherlands Max Planck Inst Informat Saarbrucken Germany

ISBN: (纸本)9781467343831

The existence of a polynomial kernel for Odd Cycle Transversal was a notorious open problem in parameterized complexity. Recently, this was settled by the present authors (Kratsch and Wahlstrom, SODA 2012), with a randomized polynomial kernel for the problem, using matroid theory to encode flow questions over a set of terminals in size polynomial in the number of terminals (rather than the total graph size, which may be superpolynomially larger). In the current work we further establish the usefulness of matroid theory to kernelization by showing applications of a result on representative sets due to Lovasz (Combinatorial Surveys 1977) and Marx (TCS 2009). We show how representative sets can be used to give a polynomial kernel for the elusive Almost 2-sat problem (where the task is to remove at most k clauses to make a 2-CNF formula satisfiable), solving a major open problem in kernelization. We further apply the representative sets tool to the problem of finding irrelevant vertices in graph cut problems, that is, vertices which can be made undeletable without affecting the status of the problem. This gives the first significant progress towards a polynomial kernel for the Multiway Cut problem;in particular, we get a polynomial kernel for Multiway Cut instances with a bounded number of terminals. Both these kernelization results have significant spin-off effects, producing the first polynomial kernels for a range of related problems. More generally, the irrelevant vertex results have implications for covering min-cuts in graphs. In particular, given a directed graph and a set of terminals, we can find a set of size polynomial in the number of terminals (a cut-covering set) which contains a minimum vertex cut for every choice of sources and sinks from the terminal set. Similarly, given an undirected graph and a set of terminals, we can find a set of vertices, of size polynomial in the number of terminals, which contains a minimum multiway cut for every partition of t

关键词： kernelization parameterized complexity matroids graph cuts multiway cut almost 2-sat

来源：评论

学校读者我要写书评

暂无评论

Lower Bounds on the complexity of MSO₁ Model-Checking

Lower Bounds on the Complexity of MSO<sub>1</sub> Model-Chec...

引用

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

作者： Ganian, Robert Hlineny, Petr Langer, Alexander Obdrzalek, Jan Rossmanith, Peter Sikdar, Somnath Masaryk Univ Fac Informat Brno Czech Republic Rhein Westfal TH Aachen Theoret Comp Sci Aachen Germany

ISBN: (纸本)9783939897354

One of the most important algorithmic meta-theorems is a famous result by Courcelle, which states that any graph problem definable in monadic second-order logic with edge-set quantifications (MSO2) is decidable in linear time on any class of graphs of bounded tree-width. In the parlance of parameterized complexity, this means that MSO2 model-checking is fixed-parameter tractable with respect to the tree-width as parameter. Recently, Kreutzer and Tazari [13] proved a corresponding complexity lower-bound-that MSO2 model-checking is not even in XP wrt. the formula size as parameter for graph classes that are subgraph-closed and whose tree-width is poly-logarithmically unbounded. Of course, this is not an unconditional result but holds modulo a certain complexity-theoretic assumption, namely, the Exponential Time Hypothesis (ETH). In this paper we present a closely related result. We show that even MSO1 model-checking with a fixed set of vertex labels, but without edge-set quantifications, is not in XP wrt. the formula size as parameter for graph classes which are subgraph-closed and whose tree-width is poly-logarithmically unbounded unless the non-uniform ETH fails. In comparison to Kreutzer and Tazari, (1) we use a stronger prerequisite, namely non-uniform instead of uniform ETH, to avoid the effectiveness assumption and the construction of certain obstructions used in their proofs;and (2) we assume a different set of problems to be efficiently decidable, namely MSO1 -definable properties on vertex labeled graphs instead of MSO2-definable properties on unlabeled graphs. Our result has an interesting consequence in the realm of digraph width measures: Strengthening the recent result [8], we show that no subdigraph-monotone measure can be algorithmically useful, unless it is within a poly-logarithmic factor of (undirected) tree-width.

关键词： Monadic Second-Order Logic Treewidth Lower Bounds Exponential Time Hypothesis parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：