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

fixed-parameter tractable Distances to Sparse Graph Classes

ALGORITHMICA 2017年第1期79卷 139-158页

作者： Bulian, Jannis Dawar, Anuj Univ Cambridge Comp Lab Cambridge England

We show that for various classes of sparse graphs, and several measures of distance to such classes (such as edit distance and elimination distance), the problem of determining the distance of a given graph G to is fixed-parameter tractable. The results are based on two general techniques. The first of these, building on recent work of Grohe et al. establishes that any class of graphs that is slicewise nowhere dense and slicewise first-order definable is . The second shows that determining the elimination distance of a graph G to a minor-closed class is . We demonstrate that several prior results (of Golovach, Moser and Thilikos and Mathieson) on the fixed-parameter tractability of distance measures are special cases of our first method.

关键词： fixed-parameter tractable parameterized complexity Graph theory Sparse graphs Nowhere dense Excluded minor Minor-closed Deletion distance Elimination distance Distance

来源：评论

学校读者我要写书评

暂无评论

Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Caratheodory

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2017年第1期83卷 207-214页

作者： Onn, Shmuel Technion Israel Inst Technol Haifa Israel

The three-way table problem is to decide if there exists an 1 x m x n table satisfying given line sums, and find a table if yes. Recently, it was shown to be fixed-parameter tractable with parameters 1, m. Here we extend this and show that the huge version of the problem, where the variable side n is encoded in binary, is also fixed-parameter tractable with parameters 1, m. We also conclude that the huge multicommodity flow problem with a huge number of consumers is fixed-parameter tractable. One of our tools is a theorem about unimodular monoids which is of interest on its own right. (C) 2016 Elsevier Inc. All rights reserved.

关键词： Integer programming Integer Caratheodory Multiway table Bin packing Cutting stock fixed-parameter tractable Totally unimodular Multicommodity flow

来源：评论

学校读者我要写书评

暂无评论

BALANCED JUDICIOUS BIPARTITION IS fixed-parameter tractable

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2019年第4期33卷 1878-1911页

作者： Lokshtanov, Daniel Saurabh, Saket Sharma, Roohani Zehavi, Meirav Univ Bergen Inst Informat Bergen Norway HBNI Inst Math Sci Chennai Tamil Nadu India UMI ReLax Paris France Ben Gurion Univ Negev Beer Sheva Israel

The family of judicious partitioning problems, introduced by Bollobas and Scott to the field of extremal combinatorics, has been extensively studied from a structural point of view for over two decades. This rich realm of problems aims to counterbalance the objectives of classical partitioning problems such as MIN CUT, MIN BISECTION, and MAX CUT. While these classical problems focus solely on the minimization/maximization of the number of edges crossing the cut, judicious (bi)partitioning problems ask the natural question of the minimization/maximization of the number of edges lying in the (two) sides of the cut. In particular, JUDICIOUS BIPARTITION (JB) seeks a bipartition that is \judicious" in the sense that neither side is burdened by too many edges, and BALANCED JB (BJB) also requires that the sizes of the sides themselves are \balanced" in the sense that neither of them is too large. Both of these problems were defined in the work by Bollobas and Scott and have received notable scientific attention since then. In this paper, we shed light on the study of judicious partitioning problems from the viewpoint of algorithm design. Specifically, we prove that BJB is fixed parameter tractable (FPT) (which also proves that JB is FPT).

关键词： judicious partition fixed-parameter tractable minimum bisection tree decomposition randomized contractions

来源：评论

学校读者我要写书评

暂无评论

Dynamic coloring on restricted graph classes

引用

THEORETICAL COMPUTER SCIENCE 2025年 1043卷

作者： Bhyravarapu, Sriram Kumari, Swati Reddy, I. Vinod Indian Inst Technol Guwahati Gauhati India IIT Bhilai Dept Comp Sci & Engn Bhilai India

A proper k-coloring of a graph is an assignment of colors from the set {1, 2, ... , k} to the vertices of the graph such that no two adjacent vertices receive the same color. Given a graph G and an integer k, the DYNAMIC COLORING problem asks whether there exists a proper k-coloring of G such that for every vertex v of degree at least two, there exists at least two distinct colors appearing in the neighborhood of v. The minimum integer k such that there exists a dynamic coloring of G using k colors is called the dynamic chromatic number of G, denoted by xd(G). The problem is NP-complete in general but is solvable in polynomial time on trees and graphs of bounded tree-width. In this paper, we study the problem on restricted classes of graphs. We show that the problem can be solved in polynomial time on chordal graphs and biconvex bipartite graphs. On the other hand, we prove that it is NP-complete on star-convex bipartite graphs, comb-convex bipartite graphs and perfect elimination bipartite graphs. Next, we initiate the study of DYNAMIC COLORING from the perspective of parameterized complexity. We show that the problem is W[1]-hard when parameterized by clique-width and we present a fixed-parameter tractable algorithm parameterized by the combined parameters clique-width and the number of colors. We also show that the problem is fixed-parameter tractable when parameterized by neighborhood diversity or twin-cover.

关键词： Proper coloring fixed-parameter tractable NP-complete Dynamic coloring Clique-width Neighborhood diversity Twin-cover Bipartite graphs

来源：评论

学校读者我要写书评

暂无评论

Improved kernels for triangle packing in tournaments

引用

Science China(Information Sciences) 2023年第5期66卷 100-113页

作者： Hanchun YUAN Qilong FENG Jianxin WANG School of Computer Science and Engineering Central South University Hunan Provincial Key Lab on Bioinformatics Central South University

Triangle packing problem has been paid lots of attention to in the literature. In this paper, we study the kernelization of the triangle packing problem in tournaments. For the parameterized arc-disjoint triangle packing problem in tournaments, we find a maximal arc-disjoint triangle packing with the number of vertices bounded by 2.5k. Based on the relation between the maximal arc-disjoint triangle packing and the vertices outside of the packing, a kernel of size 3.5k for the problem is obtained, improving the previous best one 6k. For the parameterized vertex-disjoint triangle packing problem in sparse tournaments, several new properties between the triangles in maximal vertex-disjoint triangle packing and the arcs in the feedback arc set are presented, which result in a kernel of size 7k for the problem, improving the previous best one of *** also give a 7k vertex kernel for the parameterized feedback vertex set problem in sparse *** kernelization process presented in this paper for the parameterized arc-disjoint triangle packing can be applied to solve the parameterized arc-disjoint triangle packing problem on other restricted directed graph classes.

关键词： tournaments triangle packing kernelization fixed-parameter tractable graph algorithms

来源：评论

学校读者我要写书评

暂无评论

BANDWIDTH on AT-free graphs

引用

THEORETICAL COMPUTER SCIENCE 2011年第50期412卷 7001-7008页

作者： Golovach, Petr Heggernes, Pinar Kratsch, Dieter Lokshtanov, Daniel Meister, Daniel Saurabh, Saket Univ Bergen Dept Informat N-5020 Bergen Norway Univ Paul Verlaine Metz Lab Informat Theor & Appl F-57045 Metz 1 France

We study the classical BANDWIDTH problem from the viewpoint of parametrised algorithms. Given a graph G = (V, E) and a positive integer k, the BANDWIDTH problem asks whether there exists a bijective function beta : {1.....vertical bar V vertical bar) -> V such that for every edge uv, is an element of E, vertical bar beta(-1) (u) - vertical bar beta(-1) (V) vertical bar <= k. It is known that under standard complexity assumptions, no algorithm for BANDWIDTH with running time of the form f (k)n(O(1)) exists, even when the input is restricted to trees. We initiate the search for classes of graphs where such algorithms do exist. We present an algorithm with running time n . 2(O(k log k)) for BANDWIDTH on AT-free graphs, a well-studied graph class that contains interval, permutation, and cocomparability graphs. Our result is the first non-trivial algorithm that shows fixed-parameter tractability of BANDWIDTH on a graph class on which the problem remains NP-complete. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Algorithm fixed-parameter tractable Bandwidth AT-free graph

来源：评论

学校读者我要写书评

暂无评论

fixed-parameter algorithms for the weighted Max-Cut problem on embedded 1-planar graphs

引用

THEORETICAL COMPUTER SCIENCE 2021年 852卷 172-184页

作者： Dahn, Christine Kriege, Nils M. Mutzel, Petra Schilling, Julian Univ Bonn Inst Comp Sci Bonn Germany Univ Vienna Fac Comp Sci Vienna Austria TU Dortmund Univ Dept Comp Sci Dortmund Germany

We propose two fixed-parameter tractable algorithms for the weighted MAX-CUT problem on embedded 1-planar graphs parameterized by the crossing number k of the given embedding. A graph is called 1-planar if it can be drawn in the plane with at most one crossing per edge. Our algorithms recursively reduce a 1-planar graph to at most 3(k) planar graphs, using edge removal and node contraction. Our main algorithm then solves the MAX-CUT problem for the planar graphs using the FCE-MAXCUT introduced by Liers and Pardella [23]. In the case of non-negative edge weights, we suggest a variant that allows to solve the planar instances with any planar MAX-CUT algorithm. We show that a maximum cut in the given 1-planar graph can be derived from the solutions for the planar graphs. Our algorithms compute a maximum cut in an embedded weighted 1-planar graph with n nodes and kedge crossings in time O(3(k).n(3/2) log n). (C) 2020 Elsevier B.V. All rights reserved.

关键词： Weighted maximum cut fixed-parameter tractable 1-planar graphs

来源：评论

学校读者我要写书评

暂无评论

Possible winner problems on partial tournaments: a parameterized study

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2017年第3期33卷 882-896页

作者： Yang, Yongjie Guo, Jiong Univ Saarland Saarbrucken Germany Shandong Univ Sch Comp Sci & Technol Jinan Peoples R China

We study possible winner problems related to the uncovered set and the Banks set on partial tournaments from the viewpoint of parameterized complexity. We first study a problem where given a partial tournament D and a subset X of vertices, we are asked to add some arcs to D such that all vertices in X are included in the uncovered set. We focus on two parameterizations: parameterized by |X| and parameterized by the number of arcs to be added. In addition, we study a parameterized variant of the problem which is to determine whether all vertices of X can be included in the uncovered set by reversing at most k arcs. Finally, we study some parameterizations of a possible winner problem on partial tournaments, where we are given a partial tournament D and a distinguished vertex p, and asked whether D has a maximal transitive subtournament with p being the 0-indegree vertex. These parameterized problems are related to the Banks set. We achieve results, -hardness results as well as results along with a kernelization lower bound for the problems studied in this paper.

关键词： Tournament solution Banks set Uncovered set parameterized complexity fixed-parameter tractable

来源：评论

学校读者我要写书评

暂无评论

parameterized algorithms and complexity for the traveling purchaser problem and its variants

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第4期44卷 2269-2285页

作者： Xiao, Mingyu Zhang, Jianan Lin, Weibo Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Peoples R China Huawei Technol Co Ltd Hangzhou Zhejiang Peoples R China

The traveling purchaser problem (TPP), a generalization of the traveling salesman problem, is to determine a tour of suppliers and purchase needed products from suppliers while minimizing the traveling and purchasing cost. This problem finds applications in the routing and scheduling contexts and its variants with different constraints have been widely studied. Motivated by the phenomenon that most real-world instances of TPP have a small parameter (such as the number of suppliers, the number of products to purchase, and others), we study TPP and its variants from the view of parameterized complexity. We show that TPP and some variants are fixed-parameter tractable by taking the numberkof products or the numbermof suppliers as the parameter, and W[2]-hard by taking the numberqof visited suppliers as the parameter. Furthermore, we implement some of our fixed-parameter tractable algorithms to show that they are practically effective when the parameters are not very large.

关键词： Traveling purchaser problem fixed-parameter tractable Dynamic programming parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

A constant FPT approximation algorithm for hard-capacitated k-means

引用

OPTIMIZATION AND ENGINEERING 2020年第3期21卷 709-722页

作者： Xu, Yicheng Moehring, Rolf H. Xu, Dachuan Zhang, Yong Zou, Yifei Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen 518055 Peoples R China Hefei Univ Sch Artificial Intelligence & Big Data Inst Appl Optimizat Hefei 230601 Peoples R China TU Berlin Inst Math D-10623 Berlin Germany Beijing Univ Technol Dept Operat Res & Sci Comp Beijing 100124 Peoples R China Univ Hong Kong Dept Comp Sci Pokfulam Rd Hong Kong Peoples R China

Hard-capacitated k-means (HCKM) is one of the fundamental problems remaining open in combinatorial optimization and engineering. In HCKM, one is required to partition a given n-point set into k disjoint clusters with known capacity so as to minimize the sum of within-cluster variances. It is known to be at least APX-hard, and most of the work on it has been done from a meta heuristic or bi-criteria approximation perspective. To the best our knowledge, no constant approximation algorithm or existence proof of such an algorithm is known. As our main contribution, we propose an FPT(k) approximation algorithm with constant performance guarantee for HCKM in this paper.

关键词： Approximation algorithm fixed-parameter tractable k-means clustering Capacity constraints

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：