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

38th International Symposium on Mathematical Foundations of Computer Science (MFCS)

作者： Misra, Neeldhara Panolan, Fahad Saurabh, Saket Indian Inst Sci Bangalore 560012 Karnataka India Inst Math Sci Madras Tamil Nadu India

ISBN: (纸本)9783642403132;9783642403125

The correlation clustering problem is a fundamental problem in both theory and practice, and it involves identifying clusters of objects in a data set based on their similarity. A traditional modeling of this question as a graph theoretic problem involves associating vertices with data points and indicating similarity by adjacency. Clusters then correspond to cliques in the graph. The resulting optimization problem, Cluster Editing (and several variants) are very well-studied algorithmically. In many situations, however, translating clusters to cliques can be somewhat restrictive. A more flexible notion would be that of a structure where the vertices are mutually "not too far apart", without necessarily being adjacent. One such generalization is realized by structures called s-clubs, which are graphs of diameter at most s. In this work, we study the question of finding a set of at most k edges whose removal leaves us with a graph whose components are s-clubs. Recently, it has been shown that unless Exponential Time Hypothesis fail (ETH) fails Cluster Editing (whose components are 1-clubs) does not admit sub-exponential time algorithm [STACS, 2013]. That is, there is no algorithm solving the problem in time 2 degrees((k))n(O(1)). However, surprisingly they show that when the number of cliques in the output graph is restricted to d, then the problem can be solved in time O(2(O(root dk)) + m + n). We show that this sub-exponential time algorithm for the fixed number of cliques is rather an exception than a rule. Our first result shows that assuming the ETH, there is no algorithm solving the s-Club Cluster Edge Deletion problem in time 2 degrees((k))n(O(1)). We show, further, that even the problem of deleting edges to obtain a graph with d s-clubs cannot be solved in time 2 degrees((k))n(O)(1) for any fixed s, d >= 2. This is a radical contrast from the situation established for cliques, where sub-exponential algorithms are known.

关键词： subexponential algorithms s-clubs cluster edge deletion ETH-hardness

来源：评论

学校读者我要写书评

暂无评论

Optimality Program in Segment and String Graphs

引用

ALGORITHMICA 2019年第7期81卷 3047-3073页

作者： Bonnet, Edouard Rzazewski, Pawel ENS Lyon LIP Lyon France Warsaw Univ Technol Fac Math & Informat Sci Warsaw Poland

Planar graphs are known to allow subexponential algorithms running in time 2O(<) or 2O(<logn) for most of the paradigmatic problems, while the brute-force time 2(n) is very likely to be asymptotically best on ge... 详细信息

Planar graphs are known to allow subexponential algorithms running in time 2O(<) or 2O(subexponential algorithms on the intersection graphs of curves (string graphs) or segments (segment intersection graphs) and which problems have no such algorithms under the Exponential Time Hypothesis (ETH). Among our results, we show that, quite surprisingly, 3-Coloring can also be solved in time 2O(n2/3logO(1)n) on string graphs while an algorithm running in time 2o(n) for 4-Coloring even on axis-parallel segments (of unbounded length) would disprove the ETH. For 4-Coloring of unit segments, we show a weaker lower bound, excluding a 2o(n2/3) algorithm (under the ETH). The construction exploits the celebrated Erds-Szekeres theorem. The subexponential running time also carries over to Min Feedback Vertex Set, but not to Min Dominating Set and Min Independent Dominating Set.

关键词： String graphs Segment graphs subexponential algorithms ETH

来源：评论

学校读者我要写书评

暂无评论

Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors

引用

ALGORITHMICA 2005年第4期41卷 245-267页

作者： Demaine, ED Hajiaghayi, M Thilikos, DM MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA Univ Politecn Cataluna Dept Llenguatges & Sistemes Informat E-08034 Barcelona Spain

We present a fixed-parameter algorithm that constructively solves the k-dominating set problem on any class of graphs excluding a single-crossing graph ( a graph that can be drawn in the plane with at most one crossing) as a minor in O(4(9.55rootk)n(O(1))) time. Examples of such graph classes are the K-3,K-3-minor-free graphs and the K-5-minor-free graphs. As a consequence, we extend our results to several other problems such as vertex cover, edge dominating set, independent set, clique-transversal set, kernels in digraphs, feedback vertex set, and a collection of vertex-removal problems. Our work generalizes and extends the recent results of exponential speedup in designing fixed-parameter algorithms on planar graphs due to Alber et al. to other (nonplanar) classes of graphs.

关键词： subexponential algorithms graph minors dominating set

来源：评论

学校读者我要写书评

暂无评论

New upper bounds on the decomposability of planar graphs

引用

JOURNAL OF GRAPH THEORY 2006年第1期51卷 53-81页

作者： Fomin, FV Thilikos, DM Univ Bergen Dept Informat N-5020 Bergen Norway Natl & Capodistrian Univ Athens GR-15784 Athens Greece

It is known that a planar graph on n vertices has branch-width/ tree-width bounded by alpha root n. In many algorithmic applications, it is useful to have a small bound on the constant alpha. We give a proof of the best, so far, upper bound for the constant a. In particular, for the case of tree-width, alpha < 3.182 and for the case of branch-width, alpha < 2.122. Our proof is based on the planar separation theorem of Alon, Seymour, and Thomas and some min-max theorems of Robertson and Seymour from the graph minors series. We also discuss some algorithmic consequences of this result. (c) 2005 Wiley Periodicals, Inc.

关键词： tree-width branch-width planar graphs separation theorems parameterized algorithms subexponential algorithms

来源：评论

学校读者我要写书评

暂无评论

Cyclic games and linear programming

引用

DISCRETE APPLIED MATHEMATICS 2008年第11期156卷 2195-2231页

作者： Vorobyov, Sergei Tech Univ Wien Inst Informat Syst Abteilung Datenbanken & Artificial Intelligence A-1040 Vienna Austria

New efficient algorithms for solving infinite-duration two-person adversary games with the decision problem in NP boolean AND CONP, based on linear programming (LP), LP-representations, combinatorial LP, linear comple... 详细信息

关键词： mean payoff simple stochastic parity discounted payoff games longest-shortest paths generalized linear complementarity controlled linear programming combinatorial linear programming subexponential algorithms iterative improvement local search

来源：评论

学校读者我要写书评

暂无评论

New deterministic algorithms for solving parity games

引用

DISCRETE OPTIMIZATION 2018年 30卷 73-95页

作者： Mnich, Matthias Roeglin, Heiko Roesner, Clemens Univ Bonn Dept Comp Sci Bonn Germany Maastricht Univ Dept Quantitat Econ Maastricht Netherlands

We study parity games in which one of the two players controls only a small number k of nodes and the other player controls the n - k other nodes of the game. Our main result is a fixed-parameter algorithm that solves bipartite Parity games in time k(O(root k)) . O(n(3)), and general parity games in time (p + k)(O(root k)) . O(pnm), where p is the number of distinct priorities and m is the number of edges. For all games with k = o(n) this improves the previously fastest algorithm by Jurdzinski, Paterson, and Zwick (SICOMP 2008). We also obtain novel kernelization results and an improved deterministic algorithm for graphs with small average degree. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Parity games Fixed-parameter algorithms Kernelization subexponential algorithms

来源：评论

学校读者我要写书评

暂无评论

On maximum independent sets in P₅-free graphs

引用

DISCRETE APPLIED MATHEMATICS 2010年第9期158卷 1041-1044页

作者： Randerath, Bert Schiermeyer, Ingo Cologne Univ Appl Sci Inst Commun Engn D-50679 Cologne Germany Tech Univ Bergakad Freiberg Inst Discrete Math & Algebra D-09596 Freiberg Germany

The complexity status of the Maximum Independent Set Problem (MIS) for the family of P-5-free graphs is unknown. Although for many subclasses of P-5-free graphs MIS can be solved in polynomial time, only exponential time MIS-algorithms for general graphs are known so far. In this note we present the first algorithm to solve MIS for P-5-free graphs in subexponential time. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Independent set Independence number subexponential algorithms

来源：评论

学校读者我要写书评

暂无评论

HOW TO FIND STEINER MINIMAL-TREES IN EUCLIDEAN D-SPACE

引用

ALGORITHMICA 1992年第2-3期7卷 137-177页

作者： SMITH, WD 1. AT&T Bell Laboratories 07974 Murray Hill NJ USA

This paper has two purposes. The first is to present a new way to find a Steiner minimum tree (SMT) connecting N sites in d-space, d greater-than-or-equal-to 2. We present (in Appendix 1) a computer code for this purpose. This is the only procedure known to the author for finding Steiner minimal trees in d-space for d > 2, and also the first one which fits naturally into the framework of "backtracking" and "branch-and-bound." Finding SMTs of up to N = 12 general sites in d-space (for any d) now appears feasible. We tabulate Steiner minimal trees for many point sets, including the vertices of most of the regular and Archimedean d-polytopes with less-than-or-equal-to 16 vertices. As a consequence of these tables, the Gilbert Pollak conjecture is shown to be false in dimensions 3-9. (The conjecture remains open in other dimensions;it is probably false in all dimensions d with d greater-than-or-equal-to 3, but it is probably true when d = 2.) The second purpose is to present some new theoretical results regarding the asymptotic computational complexity of finding SMTs to precision-epsilon. We show that in two-dimensions, Steiner minimum trees may be found exactly in exponential time O(C(N)) on a real RAM. (All previous provable time bounds were superexponential.) If the tree is only wanted to precision-epsilon, then there is an (N/epsilon)O(square-root N)-time algorithm, which is subexponential if 1/epsilon grows only polynomially with N. Also, the rectilinear Steiner minimal tree of N points in the plane may be found in N(O(square-root N) time. J. S. Provan devised an O(N6/epsilon-4)-time algorithm for finding the SMT of a convex N-point set in the plane. (Also the rectilinear SMT of such a set may be found in O(N6) time.) One therefore suspects that this problem may be solved exactly in polynomial time. We show that this suspicion is in fact true if a certain conjecture about the size of "Steiner sensitivity diagrams" is correct. All of these algorithms are for a "rea

关键词： STEINER TREES GILBERT-POLLAK CONJECTURE subexponential algorithms REGULAR POLYTOPES SENSITIVITY DIAGRAMS

来源：评论

学校读者我要写书评

暂无评论

On miniaturized problems in parameterized complexity theory

引用

THEORETICAL COMPUTER SCIENCE 2006年第3期351卷 314-336页

作者： Chen, YJ Flum, J Shanghai Jiao Tong Univ BASICS Dept Comp Sci Shanghai 200030 Peoples R China Univ Freiburg Abt Math Log D-79104 Freiburg Germany

We introduce a general notion of miniaturization of a problem that comprises the different miniaturizations of concrete problems considered so far. We develop parts of the basic theory of miniaturizations. Using the appropriate logical formalism, we show that the miniaturization of a definable problem in W[t] lies in W[t], too. In particular, the miniaturization of the dominating set problem is in W[2]. Furthermore, we investigate the relation between f (k) center dot n(o(k)) time and subexponential time algorithms for the dominating set problem and for the clique problem. (c) 2005 Elsevier B.V. All rights reserved.

关键词： parameterized complexity subexponential algorithms Fagin-definability

来源：评论

学校读者我要写书评

暂无评论

Faster approximation schemes and parameterized algorithms on (odd-)H-minor-free graphs

引用

THEORETICAL COMPUTER SCIENCE 2012年 417卷 95-107页

作者： Tazari, Siamak Humboldt Univ Dept Comp Sci D-10099 Berlin Germany

We improve the running time of the general algorithmic technique known as Baker's approach (1994) [1] on H-minor-free graphs from theta(n(integral(|H|))) to theta(integral(|H|)n(theta(1))). The numerous applications include, e.g. a 2-approximation for coloring and PTASes for various problems such as dominating set and max-cut, where we obtain similar improvements. On classes of odd-minor-free graphs, which have gained significant attention in recent time, we obtain a similar acceleration for a variant of the structural decomposition theorem proved by Demaine et al. (2010) [20]. We use these algorithms to derive faster 2-approximations;furthermore, we present the first PTASes and subexponential FPT-algorithms for independent set and vertex cover on these graph classes using a novel dynamic programming technique. We also introduce a technique to derive (nearly) subexponential parameterized algorithms on H-minor-free graphs. Our technique applies, in particular, to problems such as Steiner tree, (directed) subgraph with a property, (directed) longest path, and (connected/independent) dominating set, on some or all proper minor-closed graph classes. We obtain as a corollary that all problems with a minor-monotone subexponential kernel and amenable to our technique can be solved in subexponential FPT-time on H-minor free graphs. This results in a general methodology for subexponential parameterized algorithms outside the framework of bidimensionality. (C) 2011 Elsevier B.V. All rights reserved.

关键词： subexponential algorithms Graph minors Odd minors

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：