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

50th International Workshop on Graph-Theoretic Concepts in Computer Science

作者： Keeney, Ryan Lokshtanov, Daniel Univ Calif Santa Barbara Santa Barbara CA 93106 USA

ISBN: (纸本)9783031754081;9783031754098

For a digraph G and ordering of G, the degreewidth of the ordering is the maximum number of backward arcs incident to any vertex of G. The degreewidth Delta(G) of G is defined as the minimum degreewidth of an ordering of G. A digraph G is semi-complete if every pair of vertices is connected by at least one arc, oriented if every pair of vertices is connected by at most one arc, and a tournament if every pair of vertices is connected by exactly one arc. We give a fixed parameter tractable (FPT) algorithm, with running time Delta(G)(O(Delta(G)))n+ O(n(2)), to compute the degreewidth of semi-complete digraphs. We then show that both the FEEDBACK ARC SET and CUTWIDTH problems on semi-complete digraphs admit algorithms with running time Delta(G)(O(Delta(G)))n + O(n(2)). Our algorithms resolve in the affirmative two open problems of Davot et al. [WG 2023], who asked whether there exists an FPT algorithm to compute the degreewidth of a tournament, and whether FEEDBACK ARC SET on tournaments admits an FPT algorithm when parameterized by the degreewidth of the input digraph. Additionally, extending an argument of Davot et al. [WG 2023], we show that sorting by in-degree is a 3-approximation algorithm for degreewidth on semi-complete digraphs. Finally we prove that it is NP-hard to determine whether a given oriented digraph has degreewidth at most 2.

关键词： Semi-complete digraph parameterized algorithm degreewidth feedback arc set cutwidth

来源：评论

学校读者我要写书评

暂无评论

FPT Approximation for Capacitated Sum of Radii 15

FPT Approximation for Capacitated Sum of Radii

引用

15th Innovations in Theoretical Computer Science Conference (ITCS)

作者： Jaiswal, Ragesh Kumar, Amit Yadav, Jatin IIT Delhi CSE Delhi India

ISBN: (纸本)9783959773096

We consider the capacitated clustering problem in general metric spaces where the goal is to identify k clusters and minimize the sum of the radii of the clusters (we call this the CAPACITATED k-sumRADii problem). We are interested in fixed-parameter tractable (FPT) approximation algorithms where the running time is of the form f (k) " poly(n), where f (k) can be an exponential function of k and n is the number of points in the input. In the uniform capacity case, Bandyapadhyay et al. recently gave a 4-approximation algorithm for this problem. Our first result improves this to an FPT 3-approximation and extends to a constant factor approximation for any Lp norm of the cluster radii. In the general capacities version, Bandyapadhyay et al. gave an FPT 15-approximation algorithm. We extend their framework to give an FPT (4-V13)-approximation algorithm for this problem. Our framework relies on a novel idea of identifying approximations to optimal clusters by carefully pruning points from an initial candidate set of points. This is in contrast to prior results that rely on guessing suitable points and building balls of appropriate radii around them. On the hardness front, we show that assuming the Exponential Time Hypothesis, there is a constant c> 1 such that any c-approximation algorithm for the non-uniform capacity version of this (kproblem requires running time 2(Omega) (k/polylog(k)).

关键词： Approximation algorithm parameterized algorithm clustering

来源：评论

学校读者我要写书评

暂无评论

On the complexity of and solutions to the minimum stopping and trapping set problems

引用

THEORETICAL COMPUTER SCIENCE 2022年 915卷 26-44页

作者： Velasquez, Alvaro Subramani, K. Wojciechowski, Piotr AF Res Lab Informat Directorate Rome NY 13441 USA West Virginia Univ LCSEE Morgantown WV 26506 USA

In this paper, we discuss the problems of finding minimum stopping sets and trapping sets in Tanner graphs, using integer linear programming. These problems are important for establishing reliable communication across noisy channels. Indeed, stopping sets and trapping sets correspond to combinatorial structures in information-theoretic codes, which lead to errors in decoding once a message is received. In particular, these sets correspond to variables that are not eventually corrected by the decoder, thus causing failures in decoding when using iterative algorithms. We present integer linear programs (ILPs) for finding stopping sets and several trapping set variants. Furthermore, we prove that two of these trapping set problem variants are NP-hard for the first time. Additionally, we analyze these variants from the parameterized perspective. Finally, we model stopping set and trapping set problems as Integer Linear Programs (ILPs). The effectiveness of our approach is demonstrated by finding stopping sets of size up to 48 in the (4896, 2474) Margulis code. This compares favorably to the current state-of-the-art, which finds stopping sets of size up to 26. For the trapping set problems, we show for which cases an ILP produces solutions efficiently and for which cases it performs poorly. The proposed approach is applicable to codes represented by regular and irregular graphs alike.(1) (c) 2022 Elsevier B.V. All rights reserved.

关键词： Stopping set Trapping set NP-complete parameterized algorithm Exact exponential algorithm

来源：评论

学校读者我要写书评

暂无评论

Vertex partitioning problems on graphs with bounded tree width

引用

DISCRETE APPLIED MATHEMATICS 2022年 319卷 254-270页

作者： Aravind, N. R. Kalyanasundaram, Subrahmanyam Kare, Anjeneya Swami Indian Inst Technol Hyderabad Dept CSE Hyderabad India Univ Hyderabad Hyderabad India

In an undirected graph, a matching cut is a partition of vertices into two sets such that the edges across the sets induce a matching. The MATCHING CUT problem is the problem of deciding whether a given graph has a matching cut. Let H be a fixed undirected graph. A vertex coloring of an undirected input graph G is said to be an H -FREE COLORING if none of the color classes contain H as an induced subgraph. The H -FREE CHROMATIC NUMBER of G is the minimum number of colors required for an H -FREE COLORING of G. Both The MATCHING CUT problem and the H -FREE COLORING problem can be expressed using a monadic second-order logic (MSOL) formula and hence is solvable in linear time for graphs with bounded tree-width. However, this approach leads to a running time of f (||phi||, t)n(O(1)), where ||phi|| is the length of the MSOL formula, t is the tree-width of the graph and n is the number of vertices of the graph. The dependency of f (||phi||, t) on ||phi|| can be as bad as a tower of exponentials. In this paper, we provide explicit combinatorial FPT algorithms for MATCHING CUT problem and H -FREE COLORING problem, parameterized by the tree-width of G. The single exponential FPT algorithm for the MATCHING CUT problem answers an open question posed by Kratsch and Le (2016). The techniques used in the paper are also used to provide an FPT algorithm for a variant of H-free coloring, where H is forbidden as a subgraph (not necessarily induced) in the color classes of G. (c) 2021 Elsevier B.V. All rights reserved.

关键词： Matching cut Decomposable graphs H -free coloring parameterized algorithm

来源：评论

学校读者我要写书评

暂无评论

A Polynomial Kernel for Funnel Arc Deletion Set

引用

algorithmICA 2022年第8期84卷 2358-2378页

作者： Milani, Marcelo Garlet Inst Software Engn & Theoret Comp Sci Log & Semant Ernst Reuter Pl 7 D-10587 Berlin Germany

In DIRECTED FEEDBACK ARC SET (DFAS) we search for a set of at most k arcs which intersect every cycle in the input digraph. It is a well-known open problem in parameterized complexity to decide if DFAS admits a kernel of polynomial size. We consider C-ARC DELETION SET (C-ADS), a variant of DFAS where we want to remove at most k arcs from the input digraph in order to turn it into a digraph of a class C. In this work, we choose C to be the class of funnels. FUNNEL-ADS is NP-hard even if the input is a DAG, but is fixed-parameter tractable with respect to k. So far no polynomial kernels for this problem were known. Our main result is a kernel for FUNNEL-ADS with O(k(6)) many vertices and O(k(7)) many arcs, computable in O(nm) time, where n is the number of vertices and m the number of arcs in the input digraph.

关键词： Graph editing Directed feedback arc set parameterized algorithm Kernels Funnels

来源：评论

学校读者我要写书评

暂无评论

Improved parameterized algorithms for Network Query Problems

引用

algorithmICA 2019年第6期81卷 2270-2316页

作者： Pinter, Ron Y. Shachnai, Hadas Zehavi, Meirav Technion Dept Comp Sci IL-3200003 Haifa Israel

In the Partial Information Network Query (PINQ) problem, we are given a host graph H, and a pattern P whose topology is partially known. We seek a connected subgraph of H that resemblesP. PINQ is a generalization of Subgraph Isomorphism, where the topology of P is known, and Graph Motif, where the topology of P is unknown. This generalization addresses the major challenge of analyzing biological networks in the absence of certain topological data. In this paper, we use a non-standard hybridization of algebraic and combinatorial tools to develop an exact parameterized algorithm as well as an FPT-approximation scheme for PINQ.

关键词： parameterized algorithm Narrow sieves Partial information network query Alignment network query Graph motif

来源：评论

学校读者我要写书评

暂无评论

Improved parameterized Approximation for Balanced k-Median 15th

Improved Parameterized Approximation for Balanced <i>k</i>-M...

引用

15th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Zhang, Zhen Feng, Qilong Hunan Univ Technol & Business Sch Frontier Crossover Studies Changsha 410000 Peoples R China Cent South Univ Sch Comp Sci & Engn Changsha 410000 Peoples R China

ISBN: (纸本)9783030926816;9783030926809

Balanced k-median is a frequently encountered problem in applications requiring balanced clustering results, which generalizes the standard k-median problem in that the number of clients connected to each facility is constrained by the given lower and upper bounds. This problem is known to be W[2]-hard if parameterized by k, implying that the existence of an FPT(k)-time exact algorithm is unlikely. In this paper, we give a (3 + epsilon)-approximation algorithm for balanced k-median that runs in FPT(k) time, improving upon the previous best approximation ratio of 7.2 + epsilon obtained in the same time. The crucial step in getting the improved ratio and our main technical contribution is a different random sampling method for selecting opened facilities.

关键词： Approximation algorithm parameterized algorithm k-median

来源：评论

学校读者我要写书评

暂无评论

Dividing Splittable Goods Evenly and With Limited Fragmentation

引用

algorithmICA 2020年第5期82卷 1298-1328页

作者： Damaschke, Peter Chalmers Univ Dept Comp Sci & Engn S-41296 Gothenburg Sweden

A splittable good provided in n pieces shall be divided as evenly as possible among m agents, where every agent can take shares from at most F pieces. We call F the fragmentation and mainly restrict attention to the cases F = 1 and F = 2. For F = 1, the max-min and min-max problems are solvable in linear time. The case F = 2 has neat formulations and structural characterizations in terms of weighted graphs. First we focus on perfectly balanced solutions. While the problem is strongly NP-hard in general, it can be solved in linear time if m = n - 1, and a solution always exists in this case, in contrast to F = 1. Moreover, the problem is fixed-parameter tractable in the parameter 2m - n. (Note that this parameter measures the number of agents above the trivial threshold m = n/2.) The structural results suggest another related problem where unsplittable items shall be assigned to subsets so as to balance the average sizes (rather than the total sizes) in these subsets. We give an approximationpreserving reduction from our original splitting problem with fragmentation F = 2 to this averaging problem, and some approximation results in cases when m is close to either n or n/2.

关键词： Fair division Weighted graph Linear-time algorithm parameterized algorithm Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A 2^O ^(k) n algorithm for k-cycle in minor-closed graph families

引用

THEORETICAL COMPUTER SCIENCE 2020年 842卷 74-85页

作者： Yuster, Raphael Univ Haifa Dept Math IL-31905 Haifa Israel

Let C be a proper minor-closed family of graphs. We present a randomized algorithm that given a graph G is an element of C with n vertices, finds a simple cycle of size k in G (if exists) in 2(O(k))n time. The algorithm applies to both directed and undirected graphs. In previous linear time algorithms for this problem, the runtime dependence on k is super-exponential. The algorithm can be derandomized yielding a 2(O(k))n log n time algorithm. (C) 2020 Elsevier B.V. All rights reserved.

关键词： k-cycle Minor-closed graph family parameterized algorithm Linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

Randomized parameterized algorithms for the Kidney Exchange Problem

引用

algorithmS 2019年第2期12卷 50-50页

作者： Lin, Mugang Wang, Jianxin Feng, Qilong Fu, Bin Cent S Univ Sch Comp Sci & Engn Changsha 410083 Hunan Peoples R China Hengyang Normal Univ Sch Comp Sci & Technol Hengyang 421002 Peoples R China Hunan Prov Key Lab Intelligent Informat Proc & Ap Hengyang 421002 Peoples R China Univ Texas Rio Grande Valley Dept Comp Sci Edinburg TX 78539 USA

In order to increase the potential kidney transplants between patients and their incompatible donors, kidney exchange programs have been created in many countries. In the programs, designing algorithms for the kidney exchange problem plays a critical role. The graph theory model of the kidney exchange problem is to find a maximum weight packing of vertex-disjoint cycles and chains for a given weighted digraph. In general, the length of cycles is not more than a given constant L (typically 2 <= L <= 5), and the objective function corresponds to maximizing the number of possible kidney transplants. In this paper, we study the parameterized complexity and randomized algorithms for the kidney exchange problem without chains from theory. We construct two different parameterized models of the kidney exchange problem for two cases L = 3 and L >= 3, and propose two randomized parameterized algorithms based on the random partitioning technique and the randomized algebraic technique, respectively.

关键词： kidney exchange problem randomized algorithm parameterized algorithm random partitioning multilinear monomial detection

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：