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

arXiv 2018年

作者： Fleischner, Herbert Chia, Gek L. Institute of Logic and Computation Algorithms and Complexity Group Technical University of Vienna Austria Department of Mathematical and Actuarial Sciences Lee Kong Chian Faculty of Engineering and Science Universiti Tunku Abdul Rahman Sungai Long Campus Jalan Sungai Long Bandar Sungai Long Cheras KajangSelangor43000 Malaysia Institute of Mathematical Sciences University of Malaya Kuala Lumpur50603 Malaysia

This is the second part of joint research in which we show that every 2-connected graph G has the F4 property. That is, given distinct xi ∈ V (G), 1 ≤ i ≤ 4, there is an x1x2-hamiltonian path in G2 containing different edges x3y3, x4y4 ∈ E(G) for some y3, y4 ∈ V (G). However, it was shown already in [3, Theorem 2] that 2-connected DT-graphs have the F4 property;based on this result we generalize it to arbitrary 2-connected graphs. We also show that these results are best possible. Copyright © 2018, The Authors. All rights reserved.

关键词： Hamiltonians

来源：评论

学校读者我要写书评

暂无评论

Partitioning graph drawings and triangulated simple polygons into greedily routable regions

引用

International Journal of Computational Geometry and Applications 2017年第1-2期27卷 121-158页

作者： Nöllenburg, Martin Prutkin, Roman Rutter, Ignaz Algorithms and Complexity Group TU Wien Vienna Austria Institute of Theoretical Informatics Karlsruhe Institute of Technology Karlsruhe Germany Algorithms and Visualization WandI Technische Universiteit Eindhoven Eindhoven Netherlands

A greedily routable region (GRR) is a closed subset of ℝ2, in which any destination point can be reached from any starting point by always moving in the direction with maximum reduction of the distance to the destination in each point of the path. Recently, Tan and Kermarrec proposed a geographic routing protocol for dense wireless sensor networks based on decomposing the network area into a small number of interior-disjoint GRRs. They showed that minimum decomposition is NP-hard for polygonal regions with holes. We consider minimum GRR decomposition for plane straight-line drawings of graphs. Here, GRRs coincide with self-approaching drawings of trees, a drawing style which has become a popular research topic in graph drawing. We show that minimum decomposition is still NP-hard for graphs with cycles and even for trees, but can be solved optimally for trees in polynomial time, if we allow only certain types of GRR contacts. Additionally, we give a 2-approximation for simple polygons, if a given triangulation has to be respected. © 2017 World Scientific Publishing Company.

关键词： Decomposing graph drawings Greedy region decomposition Greedy routing in wireless sensor networks Increasing-chord drawings

来源：评论

学校读者我要写书评

暂无评论

Parameterized complexity and approximability of directed odd cycle transversal

arXiv

引用

arXiv 2017年

作者： Lokshtanov, Daniel Ramanujan, M.S. Saurabh, Saket Zehavi, Meirav University of Bergen Bergen Norway Algorithms and Complexity Group TU Wien Vienna Austria Institute of Mathematical Sciences HBNI Chennai India University of Bergen Bergen Norway

A directed odd cycle transversal of a directed graph (digraph) D is a vertex set S that intersects every odd directed cycle of D. In the Directed Odd Cycle Transversal (DOCT) problem, the input consists of a digraph D and an integer k. The objective is to determine whether there exists a directed odd cycle transversal of D of size at most k. In this paper, we settle the parameterized complexity of DOCT when parameterized by the solution size k by showing that DOCT does not admit an algorithm with running time f(k)nO(1) unless FPT = W[1]. On the positive side, we give a factor 2 fixed parameter tractable (FPT) approximation algorithm for the problem. More precisely, our algorithm takes as input D and k, runs in time 2O(k2)nO(1), and either concludes that D does not have a directed odd cycle transversal of size at most k, or produces a solution of size at most 2k. Finally, we provide evidence that there exists ϵ >0 such that DOCT does not admit a factor (1 + ϵ ) FPT-approximation algorithm. Copyright © 2017, The Authors. All rights reserved.

关键词： Directed graphs

来源：评论

学校读者我要写书评

暂无评论

On finding highly connected spanning subgraphs

arXiv

引用

arXiv 2017年

作者： Basavaraju, Manu Misra, Pranabendu Ramanujan, M.S. Saurabh, Saket Department of Computer Science and Engineering NITK Surathkal India Institute of Mathematical Sciences HBNI India Algorithms and Complexity Group TU Wien Vienna Austria Department of Informatics University of Bergen Norway

In the Survivable Network Design Problem (SNDP), the input is an edge-weighted (di)graph G and an integer ruv for every pair of vertices u, v ∈ V (G). The objective is to construct a subgraph H of minimum weight which contains ruv edge-disjoint (or node-disjoint) u-v paths. This is a fundamental problem in combinatorial optimization that captures numerous well-studied problems in graph theory and graph algorithms. An important restriction of this problem is the case when the connectivity demands are equal for every pair of vertices in the graph. In this paper, we consider the the edge-connectivity version of this problem which is called the λ-Edge Connected Subgraph (λ-ECS) problem. In this problem, we are given a λ-edge connected (di)graph G with a non-negative weight function w on the edges and an integet k, and the objective is to find a minimum weight spanning subgraph H that is also λ-edge connected, and has at upto k fewer edges than G. In other words, we are asked to compute a maximum weight subset of edges, of cardinality upto k, which may be safely deleted from G. Motivated by this question, we investigate the connectivity properties of λ-edge connected (di)graphs and obtain algorithmically significant structural results. One of our central structural results can be roughly stated as follows. In polynomial time, one can either find a set of k edges which can be deleted from the given (di)graph without violating the connectivity constraints, or correctly conclude that the (di)graph contains only O(λk3) 'interesting' edges. We demonstrate the importance of our structural results by presenting an algorithm running in time 2O(k log k)|V (G)|O(1) for λ-ECS, thus proving its fixed-parameter tractability. We follow up on this result and obtain the first polynomial compression for λ-ECS on unweighted graphs. As a consequence, we also obtain the first fixed parameter tractable algorithm, and a polynomial kernel for a parameterized version of the classic Mininum Equi

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

Counting linear extensions: Parameterizations by treewidth 24

Counting linear extensions: Parameterizations by treewidth

引用

24th Annual European Symposium on algorithms, ESA 2016

作者： Eiben, Eduard Ganian, Robert Kangas, Kustaa Ordyniak, Sebastian Algorithms and Complexity Group TU Wien Vienna Austria Helsinki Institute for Information Technology Department of Computer Science University of Helsinki Finland

ISBN: (纸本)9783959770156

We consider the #P-complete problem of counting the number of linear extensions of a poset (#LE);a fundamental problem in order theory with applications in a variety of distinct areas. In particular, we study the complexity of #LE parameterized by the well-known decompositional parameter treewidth for two natural graphical representations of the input poset, i.e., the cover and the incomparability graph. Our main result shows that #LE is fixed-parameter intractable parameterized by the treewidth of the cover graph. This resolves an open problem recently posed in the Dagstuhl seminar on Exact algorithms. On the positive side we show that #LE becomes fixed-parameter tractable parameterized by the treewidth of the incomparability graph. © Eduard Eiben, Robert Ganian, Kustaa Kangas, and Sebastian Ordyniak.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

On the complexity landscape of connected f-factor problems 41

On the complexity landscape of connected f-factor problems

引用

41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016

作者： Ganian, Robert Narayanaswamy, N.S. Ordyniak, Sebastian Rahul, C.S. Ramanujan, M.S. Algorithms and Complexity Group TU Wien Vienna Austria Indian Institute of Technology Madras Chennai India FI MU Brno Czech Republic

ISBN: (纸本)9783959770163

Given an n-vertex graph G and a function f : V (G) → {0, . . . , n-1}, an f-factor is a subgraph H of G such that degH(v) = f(v) for every vertex v ϵ V (G);we say that H is a connected f-factor if, in addition, the subgraph H is connected. A classical result of Tutte (1954) is the polynomial time algorithm to check whether a given graph has a specified f-factor. However, checking for the presence of a connected f-factor is easily seen to generalize Hamiltonian Cycle and hence is NP-complete. In fact, the Connected f-Factor problem remains NP-complete even when f(v) is at least nϵ for each vertex v and ϵ c, the problem can be solved in quasi-polynomial time in general and in randomized polynomial time if c ≤ 1. We also show that when c > 1, the problem is NP-intermediate. © Robert Ganian, Ronald de Haan, Iyad Kanj, and Stefan Szeider.

关键词： Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Symmetry properties of generalized graph truncations

arXiv

引用

arXiv 2017年

作者： Eiben, Eduard Jajcay, Robert Šparl, Primož Algorithms and Complexity Group TU Wien Vienna Austria Comenius University Bratislava Slovakia University of Primorska Institute Andrej Marušič Koper Slovenia University of Ljubljana Faculty of Education Ljubljana Slovenia Institute of Mathematics Physics and Mechanics Ljubljana Slovenia

In the generalized truncation construction, one replaces each vertex of a k-regular graph Γ with a copy of a graph Υ of order k. We investigate the symmetry properties of the graphs constructed in this way, especially in connection to the symmetry properties of the graphs Γ and Υ used in the construction. We demonstrate the usefulness of our results by using them to obtain a classification of cubic vertex-transitive graphs of girths 3, 4, and *** Codes 05C25, 05C38 Copyright © 2017, The Authors. All rights reserved.

关键词：

来源：评论

学校读者我要写书评

暂无评论

A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion 41

A single-exponential fixed-parameter algorithm for distance-...

引用

41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016

作者： Eiben, Eduard Ganian, Robert Kwon, O-Joung Algorithms and Complexity Group TU Wien Vienna Austria Institute for Computer Science and Control Hungarian Academy of Sciences Budapest Hungary FI MU Brno Czech Republic

ISBN: (纸本)9783959770163

Vertex deletion problems ask whether it is possible to delete at most k vertices from a graph so that the resulting graph belongs to a specified graph class. Over the past years, the parameterized complexity of vertex deletion to a plethora of graph classes has been systematically researched. Here we present the first single-exponential fixed-parameter algorithm for vertex deletion to distance-hereditary graphs, a well-studied graph class which is particularly important in the context of vertex deletion due to its connection to the graph parameter rank-width. We complement our result with matching asymptotic lower bounds based on the exponential time hypothesis. © Stefan Fafianie, Eva-Maria C. Hols, Stefan Kratsch, and Vuong A. Quyen.

关键词： Parameter estimation

来源：评论

学校读者我要写书评

暂无评论

Evaluation of labeling strategies for rotating maps

引用

ACM Journal of Experimental Algorithmics 2016年第2期21卷 1–21页

作者： Gemsa, Andreas Nöllenburg, Martin Rutter, Ignaz Institute of Theoretical Informatics Karlsruhe Institute of Technology Am Fasanengarten 5 Karlsruhe 76131 Germany Algorithms and Complexity Group (E186/1) TU Wien Favoritenstraße 9-11 Vienna 1040 Austria

We consider the following problem of labeling points in a dynamicmap that allows *** are given a set of feature points in the plane labeled by a set of mutually disjoint labels, where each label is an axis-aligned rectangle attached with one corner to its respective point. We require that each label remains horizontally aligned during the map rotation, and our goal is to find a set of mutually nonoverlapping visible labels for every rotation angle α ∈ [0, 2π) so that the number of visible labels over a fullmap rotation of 2π is maximized. We discuss and experimentally evaluate several labeling strategies that define additional consistency constraints on label visibility to reduce flickering effects during monotone map rotation. We introduce three heuristic algorithms and compare them experimentally to an existing approximation algorithm and exact solutions obtained from an integer linear program. Our results show that on the one hand, low flickering can be achieved at the expense of only a small reduction in the objective value, and on the other hand, the proposed heuristics achieve a high labeling quality significantly faster than the other methods. © 2016 ACM.

关键词： Consistency model Dynamic map labeling Experimental evaluation Map rotations

来源：评论

学校读者我要写书评

暂无评论

Solving problems on graphs of high rank-width 14th

Solving problems on graphs of high rank-width

引用

14th International Symposium on algorithms and Data Structures, WADS 2015

作者： Eiben, Eduard Ganian, Robert Szeider, Stefan Algorithms and Complexity Group Institute of Computer Graphics and Algorithms TU Wien Vienna Austria

ISBN: (纸本)9783319218397

A modulator of a graph G to a specified graph class H is a set of vertices whose deletion puts G into H. The cardinality of a modulator to various graph classes has long been used as a structural parameter which can be exploited to obtain FPT algorithms for a range of hard problems. Here we investigate what happens when a graph contains a modulator which is large but "well-structured" (in the sense of having bounded rank-width). Can such modulators still be exploited to obtain efficient algorithms? And is it even possible to find such modulators efficiently? We first show that the parameters derived from such well-structured modulators are strictly more general than the cardinality of modulators and rank-width itself. Then, we develop an FPT algorithm for finding such well-structured modulators to any graph class which can be characterized by a finite set of forbidden induced subgraphs. We proceed by showing how well-structured modulators can be used to obtain efficient parameterized algorithms for MINIMUM VERTEX COVER and MAXIMUM CLIQUE. Finally, we use the concept of well-structured modulators to develop an algorithmic meta-theorem for efficiently deciding problems expressible in Monadic Second Order (MSO) logic, and prove that this result is tight in the sense that it cannot be generalized to LinEMSO problems. © Springer International Publishing Switzerland 2015.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：