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

Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential algorithms

ALGORITHMICA 2011年第4期60卷 987-1003页

作者： Koutsonas, Athanassios Thilikos, Dimitrios M. Univ Athens Athens 15784 Greece

The Planar Feedback Vertex Set problem asks whether an n-vertex planar graph contains at most k vertices meeting all its cycles. The Face Cover problem asks whether all vertices of a plane graph G lie on the boundary of at most k faces of G. Standard techniques from parameterized algorithm design indicate that both problems can be solved by sub-exponential parameterized algorithms (where k is the parameter). In this paper we improve the algorithmic analysis of both problems by proving a series of combinatorial results relating the branchwidth of planar graphs with their face cover. Combining this fact with duality properties of branchwidth, allows us to derive analogous results on feedback vertex set. As a consequence, it follows that Planar Feedback Vertex Set and Face Cover can be solved in O(2(15.11).root(k) + n(2)) and O(2(10.1).root(k) + n(2)) steps, respectively.

关键词： Branchwidth parameterized algorithms Feedback vertex set Face cover

来源：评论

学校读者我要写书评

暂无评论

A faster fixed parameter algorithm for two-layer crossing minimization

引用

INFORMATION PROCESSING LETTERS 2016年第9期116卷 547-549页

作者： Kobayashi, Yasuaki Tamaki, Hisao Gakushuin Univ Toshima Ku 1-5-1 Mejiro Tokyo 1718588 Japan Meiji Univ Tama Ku 1-1-1 Higashimita Kawasaki Kanagawa 2148571 Japan Kyoto Univ Sakyo Ku Kyoto 6068501 Japan

We give an algorithm that decides whether the bipartite crossing number of a given graph is at most k. The running time of the algorithm is upper bounded by 2(O(k)) + n(O(1)), where n is the number of vertices of the input graph, which improves the previously known algorithm due to Kobayashi et al. (TCS 2014) that runs in 2(O(klogk)) + n(O(1)) time. This result is based on a combinatorial upper bound on the number of two-layer drawings of a connected bipartite graph with a bounded crossing number. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Bipartite crossing number Graph algorithms Graph drawing parameterized algorithms Two-layer crossing minimization

来源：评论

学校读者我要写书评

暂无评论

Kernels for feedback arc set in tournaments

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2011年第6期77卷 1071-1078页

作者： Bessy, Stephane Fomin, Fedor V. Gaspers, Serge Paul, Christophe Perez, Anthony Saurabh, Saket Thomasse, Stephan Univ Montpellier 2 LIRMM CNRS F-34932 Montpellier France Univ Bergen Dept Informat N-5020 Bergen Norway Univ Chile CMM Santiago 8370459 Chile Inst Math Sci Madras 600113 Tamil Nadu India

A tournament T = (V, A) is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on n vertices and an integer parameter k, the FEEDBACK ARC SET problem asks whether the given digraph has a set of k arcs whose removal results in an acyclic digraph. The FEEDBACK ARC SET problem restricted to tournaments is known as the k-FEEDBACK ARC SET IN TOURNAMENTS (k-FAST) problem. In this paper we obtain a linear vertex kernel for k-FAST. That is, we give a polynomial time algorithm which given an input instance T to k-FAST obtains an equivalent instance T' on O(k) vertices. In fact, given any fixed epsilon > 0, the kernelized instance has at most (2 + epsilon)k vertices. Our result improves the previous known bound of O(k(2)) on the kernel size for k-FAST. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for k-FAST. (C) 2010 Elsevier Inc. All rights reserved.

关键词： Feedback arc set Tournaments Kernelization parameterized algorithms Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite Tournaments

引用

ALGORITHMICA 2015年第1期71卷 87-97页

作者： Xiao, Mingyu Guo, Jiong Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 610054 Peoples R China Univ Saarland D-66123 Saarbrucken Germany

The k-feedback arc set problem is to determine whether there is a set F of at most k arcs in a directed graph G such that the removal of F makes G acyclic. The k-feedback arc set problems in tournaments and bipartite tournaments (k-FAST and k-FASBT) have applications in ranking aggregation and have been extensively studied from the viewpoint of parameterized complexity. By introducing a new concept called "bimodule", we provide a problem kernel with O(k (2)) vertices for k-FASBT, which improves the previous result by a factor of k.

关键词： Kernelization Feedback arc set Bipartite tournament Graph algorithms parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Clustering with partial information

引用

THEORETICAL COMPUTER SCIENCE 2010年第7-9期411卷 1202-1211页

作者： Bodlaender, Hans L. Fellows, Michael R. Heggernes, Pinar Mancini, Federico Papadopoulos, Charis Rosamond, Frances Univ Bergen Dept Informat N-5020 Bergen Norway Univ Newcastle Off DVC Res PCRU Callaghan NSW 2308 Australia Univ Utrecht Dept Informat & Comp Sci NL-3508 TC Utrecht Netherlands

The CORRELATION CLUSTERING problem, also known as the CLUSTER EDITING problem, seeks to edit a given graph by adding and deleting edges to obtain a collection of vertex-disjoint cliques, such that the editing cost is minimized. The EDGE CLIQUE PARTITIONING problem seeks to partition the edges of a given graph into edge-disjoint cliques, such that the number of cliques is minimized. Both problems are known to be NP-hard, and they have been previously studied with respect to approximation and fixed-parameter tractability. In this paper we study these two problems in a more general setting that we term fuzzy graphs, where the input graphs may have missing information, meaning that whether or not there is an edge between some pairs of vertices of the input graph can be undecided. For fuzzy graphs the CORRELATION CLUSTERING and EDGE CLIQUE PARTITIONING problems have previously been studied only with respect to approximation. Here we give parameterized algorithms based on kernelization for both problems. We prove that the CORRELATION CLUSTERING problem is fixed-parameter tractable on fuzzy graphs when parameterized by (k, r), where k is the editing cost and r is the minimum number of vertices required to cover the undecided edges. In particular we show that it has a polynomial-time reduction to a problem kernel on O(k(2) + r) vertices. We provide an analogous result for the EDGE CLIQUE PARTITIONING problem on fuzzy graphs. Using (k, r) as parameters, where k bounds the size of the partition, and r is the minimum number of vertices required to cover the undecided edges, we describe a polynomial-time kernelization to a problem kernel on O(k(4).3(r)) vertices. This implies fixed-parameter tractability for this parameterization. Furthermore we also show that parameterizing only by the number of cliques k, is not enough to obtain fixed-parameter tractability. The problem remains, in fact, NP-hard for each fixed k > 2. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Graphs parameterized algorithms Cluster editing Kernels

来源：评论

学校读者我要写书评

暂无评论

Vertex deletion on split graphs: Beyond 4-hitting set

引用

THEORETICAL COMPUTER SCIENCE 2020年 845卷 21-37页

作者： Choudhary, Pratibha Jain, Pallavi Krithika, R. Sahlot, Vibha Indian Inst Technol Jodhpur Jodhpur Rajasthan India HBNI Inst Math Sci Chennai Tamil Nadu India Indian Inst Technol Palakkad Palakkad India

Vertex deletion problems on graphs involve finding a set of minimum number of vertices whose deletion results in a graph with some specific property. In a recent study on vertex deletion problems on split graphs, it was shown that transforming a split graph to a block graph or a threshold graph using minimum number of vertex deletions isNP-hard. We call the decision version of these problems asSplit to Block Vertex Deletion(SBVD) andSplit to Threshold Vertex Deletion(STVD), respectively. In this paper, we study the parameterized complexity of these problems with the number of vertex deletions, k, as a parameter. These problems are implicit 4-HITTING SET and thus admit an algorithm with running time O* (3.0755(k)), a kernel with O(k(3)) vertices, and a 4-approximation algorithm. In this paper, we exploit the structural properties of the concerned graph classes and obtain a kernel forSBVDwith O(k(2)) vertices and FPT algorithms for SBVD and STVD with running times O* (2.3028(k)) and O*(2.7913(k)), respectively. We further give improved approximation algorithms for SBVD and STVD. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Vertex deletion problems Split graphs parameterized algorithms Kernelization Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

BIDIMENSIONALITY AND KERNELS

引用

SIAM JOURNAL ON COMPUTING 2020年第6期49卷 1397-1422页

作者： Fomin, Fedor, V Lokshtanov, Daniel Saurabh, Saket Thilikos, Dimitrios M. Univ Bergen Dept Informat N-5020 Bergen Norway Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA Inst Math Sci TCS Chennai 600113 Tamil Nadu India Univ Montpellier CNRS LIRMM F-34000 Montpellier France

Bidimensionality theory was introduced by [E. D. Demaine et al., T. ACM, 52 (2005), pp. 866-893] as a tool to obtain subexponential time parameterized algorithms on H-minor-free graphs. In [E. D. Demaine and M. Hajiaghayi, Bidimensionality: New connections between FPT algorithms and PTASs, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete algorithms (SODA), SIAM, Philadelphia, 2005, pp. 590-601] this theory was extended in order to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this work, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In particular, we prove that every minor (resp., contraction) bidimensional problem that satisfies a separation property and is expressible in Countable Monadic Second Order Logic (CMSO) admits a linear kernel for classes of graphs that exclude a fixed graph (resp., an apex graph) H as a minor. Our results imply that a multitude of bidimensional problems admit linear kernels on the corresponding graph classes. For most of these problems no polynomial kernels on H-minor-free graphs were known prior to our work.

关键词： kernelization parameterized algorithms treewidth bidimensionality

来源：评论

学校读者我要写书评

暂无评论

List-coloring - Parameterizing from triviality

引用

THEORETICAL COMPUTER SCIENCE 2020年 821卷 102-110页

作者： Arora, Pranav Banik, Aritra Paliwal, Vijay Kumar Raman, Venkatesh Media Net Bengaluru Karnataka India HBNI Natl Inst Sci Educ & Res Bhubaneswar India DE Shaw India Private Ltd Hyderabad India HBNI Inst Math Sci Chennai Tamil Nadu India

The classical graph coloring problem is given an undirected graph and the goal is to color the vertices of the graph with the minimum number of colors so that endpoints of each edge gets different colors. In list-coloring, each vertex is given a list of allowed colors with which it can be colored. Most versions of the problems are hard in several paradigms including approximation and parameterized complexity. We consider a few versions of the problems that are polynomial time solvable and try to extend the notion of feasible algorithms by parameterizing suitably in the paradigm of parameterized complexity. In particular, we provide extensions of these polynomial time solvable coloring problems that belong to the extreme ends of the parameterized complexity hierarchy including fixed-parameter tractable (FPT) class or the complexity class XP or W[1]-hard or PARA-NP-hard (i.e. NP-hard even for constant values of the parameter). Specifically, we consider generalizations of odd cycle transversal and edge bipartization in the context of list-coloring and show them fixed-parameter tractable. We also look at LIST COLORING where each list has n - k colors and the goal is to color the vertices respecting the list. We show that the problem is in the parameterized complexity class XP, when parameterized by k. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Graph coloring List coloring parameterized algorithms FPT

来源：评论

学校读者我要写书评

暂无评论

Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable

引用

ACM TRANSACTIONS ON algorithms 2015年第4期11卷 1–28页

作者： Chitnis, Rajesh Cygan, Marek Hajiaghayi, Mohammataghi Marx, Daniel Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Warsaw Inst Informat PL-02097 Warsaw Poland Hungarian Acad Sci Inst Comp Sci & Control H-1111 Budapest Hungary

Given a graph G and an integer k, the FEEDBACK VERTEX SET (FVS) problem asks if there is a vertex set T of size at most k that hits all cycles in the graph. The first fixed-parameter algorithm for FVS in undirected graphs appeared in a monograph of Mehlhorn in 1984. The fixed-parameter tractability (FPT) status of FVS in directed graphs was a long-standing open problem until Chen et al. (STOC '08, JACM '08) showed that it is fixed-parameter tractable by giving a 4(k)k! . n(O(1)) time algorithm. There are two subset versions of this problems: We are given an additional subset S of vertices (resp., edges), and we want to hit all cycles passing through a vertex of S (resp., an edge of S);the two variants are known to be equivalent in the parameterized sense. Recently, the SUBSET FVS problem in undirected graphs was shown to be FPT by Cygan et al. (ICALP'11, SIDMA'13) and independently by Kakimura et al. (SODA '12). We generalize the result of Chen et al. (STOC '08, JACM '08) by showing that a SUBSET FVS in directed graphs can be solved in time 2(O(k3)) . n(O(1)) (i.e., FPT parameterized by size k of the solution). By our result, we complete the picture for FVS problems and their subset versions in undirected and directed graphs. The technique of random sampling of important separators was used by Marx and Razgon (STOC '11, SICOMP '14) to show that UNDIRECTED MULTICUT is FPT, and it was generalized by Chitnis et al. (SODA '12, SICOMP '13) to directed graphs to show that DIRECTEDMULTIWAY CUT is FPT. In addition to proving the FPT of a DIRECTED SUBSET FVS, we reformulate the random sampling of important separators technique in an abstract way that can be used with a general family of transversal problems. We believe this general approach will be useful for showing the FPT of other problems in directed graphs. Moreover, we modify the probability distribution used in the technique to achieve better running time;in particular, this gives an improvement from 2(2O(k)) to 2(O(k

关键词： algorithms Theory parameterized algorithms important separators subset feedback vertex set directed graphs

来源：评论

学校读者我要写书评

暂无评论

Conjoint analysis to measure the perceived quality in volume rendering

引用

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 2007年第6期13卷 1664-1671页

作者： Giesen, Joachim Mueller, Klaus Schuberth, Eva Wang, Lujin Zolliker, Peter SUNY Stony Brook Stony Brook NY USA Swiss Fed Inst Technol Zurich Switzerland EMPA Dubendorf Dubendorf Switzerland

Visualization algorithms can have a large number of parameters, making the space of possible rendering results rather high-dimensional. Only a systematic analysis of the perceived quality can truly reveal the optimal setting for each such parameter. However, an exhaustive search in which all possible parameter permutations are presented to each user within a study group would be infeasible to conduct. Additional complications may result from possible parameter co-dependencies. Here, we will introduce an efficient user study design and analysis strategy that is geared to cope with this problem. The user feedback is fast and easy to obtain and does not require exhaustive parameter testing. To enable such a framework we have modified a preference measuring methodology, conjoint analysis, that originated in psychology and is now also widely used in market research. We demonstrate our framework by a study that measures the perceived quality in volume rendering within the context of large parameter spaces.

关键词： conjoint analysis parameterized algorithms volume visualization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：