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

Single-machine scheduling with fixed energy recharging times to minimize the number of late jobs and the number of just-in-time jobs: A parameterized complexity analysis

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2025年第1期324卷 40-48页

作者： Yu, Renjie Oron, Daniel Univ Sydney Business Sch Darlington NSW 2006 Australia

We study single-machine scheduling problems where processing each job requires both processing time and rechargeable energy. Subject to a predefined energy capacity, energy can be recharged after each job during a fixed recharging period. Our focus is on two due date-related scheduling criteria: minimizing the number of late jobs and maximizing the weighted number of jobs completed exactly at their due dates. This study aims to analyze the parameterized tractability of the two problems and develop fixed-parameter algorithms. with respect to three natural parameters the number of different due dates, the number of different processing times, and the number of different energy consumptions. Following the proofs of NP-hardness across several contexts, we demonstrate that both problems remain intractable when parameterized by and . To complement our results, we show that both problems become fixed-parameter tractable (FPT) when parameterized by u, and, and are solvable in polynomial time when both, Ve and, vp are constant.

关键词： Single machine parameterized complexity FPT XP W[t]

来源：评论

学校读者我要写书评

暂无评论

ON THE parameterized complexity OF COUNTING SMALL-SIZED MINIMUM (S,T)-CUTS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2023年第2期37卷 964-996页

作者： Berge, Pierre Bouaziz, Wassim Rimmel, Arpad Tomasik, Joanna Univ Paris IRIF CNRS F-75013 Paris France Univ Paris Saclay CentraleSupe F-91190 Gif Sur Yvette France Univ Paris Scalay LISN CentraleSupelec F-91400 Orsay France

The counting of minimum edge (S, T)-cuts in undirected graphs, parameterized by the size p of these cuts, is FPT. The best performance in the literature is O\ast(2O(p2)). We treat a more general problem of counting minimum (S, T)-cuts composed of vertices instead of edges. We propose an FPT algorithm with running time O\ast(2O(p log p)). As it may be applied to the edge version as well, we improve the time complexity of the minimum edge (S, T )-cuts counting.

关键词： parameterized complexity counting problems minimum (S T)-cuts

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of minimum/maximum degree vertex deletion on several special graphs

引用

Frontiers of Computer Science 2023年第4期17卷 97-107页

作者： Jia LI Wenjun LI Yongjie YANG Xueying YANG School of Information Engineering Hunan Industry PolytechnicChangsha 410036China Hunan Provincial Key Laboratory of Intelligent Processing of Big Data on Transportation School of Computer and Communication EngineeringChangsha University of Science and TechnologyChangsha 410015China Chair of Economic Theory Saarland UniversitySaarbrücken 66123Germany

In the minimum degree vertex deletion problem,we are given a graph,a distinguished vertex in the graph,and an integer κ,and the question is whether we can delete at most κ vertices from the graph so that the distinguished vertex has the unique minimum *** maximum degree vertex deletion problem is defined analogously but here we want the distinguished vertex to have the unique maximum *** is known that both problems areΨ-hard and fixed-parameter intractable with respect to some natural *** this paper,we study the(parameterized)complexity of these two problems restricted to split graphs,p-degenerate graphs,and planar *** study provides a comprehensive complexity landscape of the two problems restricted to these special graphs.

关键词： minimum degree maximum degree vertex deletion split graphs planar graphs parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

The parameterized complexity of Guarding Almost Convex Polygons

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2024年第2期71卷 358-398页

作者： Agrawal, Akanksha Knudsen, Kristine V. K. Lokshtanov, Daniel Saurabh, Saket Zehavi, Meirav Indian Inst Technol Madras Chennai India Univ Bergen Bergen Norway Univ Calif Santa Barbara Santa Barbara CA 93106 USA Inst Math Sci Chennai India Ben Gurion Univ Negev IL-84105 Beer Sheva Israel

The ART GALLERY problem is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an integer k;the task is to decide if at most k guards can be placed on points in G so that every point in C is visible to at least one guard. In the classic formulation of ART GALLERY, G and C consist of all the points within P. Other well-known variants restrict G and C to consist either of all the points on the boundary of P or of all the vertices of P. Recently, three new important discoveries dwere made: the above mentioned variants of ART GALLERY are all W[1]-hard with respect to k [Bonnet and Miltzowin 24thAnnual European Symposium onAlgorithms (Aarhus 2016)], the classic variant has an O(log k)-approximation algorithm [Bonnet and Miltzow in 33rd International Symposium on Computational Geometry (Brisbane 2017)], and it may require irrational guards [Abrahamsen et al. in 33rd International Symposium on Computational Geometry (Brisbane 2017)]. Building upon the third result, the classic variant and the case where G consists only of all the points on the boundary of P were both shown to be.R-complete [Abrahamsen et al. in 50th Annual ACMSIGACT Symposium on Theory ofComputing (LosAngeles 2018)]. Even when both G and C consist only of all the points on the boundary of P, the problem is not known to be in NP. Given the first discovery, the following question was posed by Giannopoulos [Lorentz Workshop on Fixed-Parameter Computational Geometry (Leiden 2016)]: Is ART GALLERY FPT with respect to r, the number of reflex vertices? In light of the developments above, we focus on the variant where G and C consist of all the vertices of P, called VERTEX-VERTEX ART GALLERY. Apart from being a variant of ART GALLERY, this case can also be viewed as the classic DOMINATING SET problem in the visibility graph of a polygon. In this article, we show that the answer to the question by Giannopoulos

关键词： Art gallery Reflex vertices Monotone 2-CSP parameterized complexity Fixed parameter tractability

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of the median and closest problems under some permutation metrics

引用

ALGORITHMS FOR MOLECULAR BIOLOGY 2024年第1期19卷 1-18页

作者： Cunha, Luis Sau, Ignasi Souza, Ueverton Univ Fed Fluminense Inst Comp Niteroi Brazil Inst Matematica Pura & Aplicada IMPA Rio De Janeiro Brazil Univ Montpellier LIRMM CNRS Montpellier France

Genome rearrangements are events where large blocks of DNA exchange places during evolution. The analysis of these events is a promising tool for understanding evolutionary genomics, providing data for phylogenetic reconstruction based on genome rearrangement measures. Many pairwise rearrangement distances have been proposed, based on finding the minimum number of rearrangement events to transform one genome into the other, using some predefined operation. When more than two genomes are considered, we have the more challenging problem of rearrangement-based phylogeny reconstruction. Given a set of genomes and a distance notion, there are at least two natural ways to define the "target" genome. On the one hand, finding a genome that minimizes the sum of the distances from this to any other, called the median genome. On the other hand, finding a genome that minimizes the maximum distance to any other, called the closest genome. Considering genomes as permutations of distinct integers, some distance metrics have been extensively studied. We investigate the median and closest problems on permutations over the following metrics: breakpoint distance, swap distance, block-interchange distance, short-block-move distance, and transposition distance. In biological applications some values are usually very small, such as the solution value d or the number k of input permutations. For each of these metrics and parameters d or k, we analyze the closest and the median problems from the viewpoint of parameterized complexity. We obtain the following results: NP-hardness for finding the median/closest permutation regarding some metrics of distance, even for only k=3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k = 3$$\end{document} permutations;Polynomial kernels for the problems of finding the median

关键词： Median problem Closest problem Genome rearrangements parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Immunization in the Threshold Model 16th

Parameterized Complexity of Immunization in the Threshold Mo...

引用

16th International Conference and Workshops on Algorithms and Computation

作者： Cordasco, Gennaro Gargano, Luisa Rescigno, Adele A. Univ Campania L Vanvitelli Dept Psychol Caserta Italy Univ Salerno Dept Comp Sci Fisciano Italy

ISBN: (纸本)9783030967307;9783030967314

We consider the problem of controlling the spread of harmful items in networks, such as the contagion proliferation of diseases or the diffusion of fake news. We assume the linear threshold model of diffusion where each node has a threshold that measures the node's resistance to the contagion. We study the parameterized complexity of the problem: Given a network, a set of initially contaminated nodes, and two integers k and l, is it possible to limit the diffusion to at most k other nodes of the network by immunizing at most l nodes? We consider several parameters associated with the input, including the bounds k and l, the maximum node degree Delta, the treewidth, and the neighborhood diversity of the network. We first give W[1] or W[2]-hardness results for each of the considered parameters. Then we give fixed-parameter algorithms for some parameter combinations.

关键词： parameterized complexity Contamination minimization Threshold model

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Small Weight Automorphisms and Isomorphisms

引用

ALGORITHMICA 2021年第12期83卷 3567-3601页

作者： Arvind, V Koebler, Johannes Kuhnert, Sebastian Toran, Jacobo Inst Math Sci HBNI Chennai Tamil Nadu India Humboldt Univ Inst Informat Berlin Germany Univ Ulm Inst Theoret Informat Ulm Germany

We study the parameterized complexity of computing nontrivial automorphisms of weight k for a given hypergraph X = (V, E), with k as fixed parameter, where the weight of a permutation pi is an element of S-n is the number of points moved by pi. Building on the earlier work of Schweitzer (in: Proceedings of 19th ESA, Springer, Berlin, 2011. https://***/10.1007/978-3-642-23719-5_32), we show the following results: (1) Computing nontrivial automorphisms of weight at most k for d-hypergraphs (that is, with edge-size bounded by d) remains fixed parameter tractable, with d treated as a second fixed parameter. Likewise, finding isomorphisms of weight k between d-hypergraphs X and Y (both defined on vertex set [n]) remains fixed parameter tractable. (2) For dealing with the exact weight k version of the problem, we introduce a more general algorithmic problem PERMCODE: given a permutation group G by a generating set and a fixed parameter k, is there is a nontrivial element of G with support at most (or exactly) k? We give a method for shrinking large orbits of the given group G to obtain subgroups while maintaining existence of weight at most k elements in it. An application of this yields an FPT algorithm for finding exact weight k nontrivial automorphisms in d-hypergraphs, d as second fixed parameter. (3) For hypergraphs with edges of unbounded size, we show that the problem is in FPTGI. (4) Computing d-hypergraph isomorphisms of weight exactly k is fixed parameter tractable. This requires a more complicated orbit shrinking technique.

关键词： parameterized complexity Graph automorphism Graph isomorphism

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Conflict-Free Set Cover

引用

THEORY OF COMPUTING SYSTEMS 2021年第3期65卷 515-540页

作者： Jacob, Ashwin Majumdar, Diptapriyo Raman, Venkatesh HBNI Inst Math Sci Chennai Tamil Nadu India Royal Holloway Univ London Egham Surrey England

SET COVER is one of the well-known classical NP-hard problems. We study the conflict-free version of the SET COVER problem. Here we have a universe U, a family F of subsets of U and a graph G(F) on the vertex set F and we look for a subfamily F' subset of F of minimum size that covers U and also forms an independent set in G(F). We study conflict-free SET COVER in parameterized complexity by restricting the focus to the variants where SET COVER is fixed parameter tractable (FPT). We give upper bounds and lower bounds for the running time of conflict-free version of SET COVER with and without duplicate sets along with restrictions to the graph classes of G(F). For example, when pairs of sets in F intersect in at most one element, for a solution of size k, we give an f (k)vertical bar F vertical bar(o(k)) lower bound for any computable function f assuming ETH even if G(F) is bipartite, but an O*(3(k2)) FPT algorithm (O* notation ignores polynomial factors of input) when G(F) is chordal.

关键词： parameterized complexity Set cover Fixed parameter tractability W-Hardness

来源：评论

学校读者我要写书评

暂无评论

Immunization in the Threshold Model: A parameterized complexity Study

引用

ALGORITHMICA 2023年第11期85卷 3376-3405页

作者： Cordasco, Gennaro Gargano, Luisa Rescigno, Adele A. Univ Campania Luigi Vanvitelli Dipartimento Psicol Viale Ellitt 31 I-81100 Caserta Italy Univ Salerno Dipartimento Informat Via Giovanni Paolo II 132 I-84084 Fisciano Italy

We consider the problem of keeping under control the spread of harmful items in networks, such as the contagion proliferation of diseases or the diffusion of fake news. We assume the linear threshold model of diffusion where each node has a threshold that measures the node's resistance to the contagion. We study the parameterized complexity of the problem: Given a network, a set of initially contaminated nodes, and two integers k and l, is it possible to limit the diffusion to at most k other nodes of the network by immunizing at most l nodes? We consider several parameters associated with the input, including the bounds k and l, the maximum node degree Delta, the number zeta of initially contaminated nodes, the treewidth, and the neighborhood diversity of the network. We first give W[1] or W[2]-hardness results for each of the considered parameters. Then we give fixed-parameter algorithms for some parameter combinations.

关键词： parameterized complexity Contamination minimization Threshold model

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of clustering problems for incomplete data

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2023年第1期134卷 1-19页

作者： Eiben, Eduard Ganian, Robert Kanj, Iyad Ordyniak, Sebastian Szeider, Stefan Univ London Royal Holloway London England TU Wien Vienna Austria DePaul Univ Chicago IL 60614 USA Univ Leeds Leeds England

We study fundamental clustering problems for incomplete data. Specifically, given a set of incomplete d-dimensional vectors (representing rows of a matrix), the goal is to complete the missing vector entries in a way that admits a partitioning of the vectors into at most k clusters with radius or diameter at most r. We give characterizations of the parameterized complexity of these problems with respect to the parameters k, r, and the minimum number of rows and columns needed to cover all the missing entries. We show that the considered problems are fixed-parameter tractable when parameterized by the three parameters combined, and that dropping any of the three parameters results in parameterized intractability. A byproduct of our results is that, for the complete data setting, all problems under consideration are fixed-parameter tractable parameterized by k + r. (c) 2022 Elsevier Inc. All rights reserved.

关键词： parameterized complexity Clustering Incomplete data

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：