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

A lightweight semi-centralized strategy for the massive parallelization of branching algorithms

PARALLEL COMPUTING 2023年第1期116卷

作者： Pastrana-Cruz, Andres Lafond, Manuel Univ Sherbrooke Dept Informat 2500 Blvd Univ Sherbrooke PQ J1K 2R1 Canada

Several NP-hard problems are solved exactly using exponential-time branching strategies, whether it be branch-and-bound algorithms, or bounded search trees in fixed-parameter algorithms. The number of tractable instances that can be handled by sequential algorithms is usually small, whereas massive parallelization has been shown to significantly increase the space of instances that can be solved exactly. However, previous centralized approaches require too much communication to be efficient, whereas decentralized approaches are more efficient but have difficulty keeping track of the global state of the *** this work, we propose to revisit the centralized paradigm while avoiding previous bottlenecks. In our strategy, the center has lightweight responsibilities, requires only a few bits for every communication, but is still able to keep track of the progress of every worker. In particular, the center never holds any task but is able to guarantee that a process with no work always receives the highest priority task *** strategy was implemented in a generic C++ library called GemPBA, which allows a programmer to convert a sequential branching algorithm into a parallel version by changing only a few lines of code. An experimental case study on the vertex cover problem demonstrates that some of the toughest instances from the DIMACS challenge graphs that would take months to solve sequentially can be handled within two hours with our approach.

关键词： Load balancing Vertex cover Parallel algorithms Scalable parallelism branching algorithms

来源：评论

学校读者我要写书评

暂无评论

Faster parameterized algorithm for r-pseudoforest deletion

引用

THEORETICAL COMPUTER SCIENCE 2025年 1028卷

作者： Tsur, Dekel Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

In the r-PSEUDOFOREST DELETION problem, the input is a graph G and integers k, r, and the goal is to decide whether there is a set of at most k vertices whose removal from G results in a graph in which every connected component can be made into a tree by deleting at most redges. In this paper we give an O<^> * ((8r + 1) <^> k) time algorithm for r-PSEUDOFOREST DELETION for every r >= 1.

关键词： Graph algorithms Parameterized complexity branching algorithms

来源：评论

学校读者我要写书评

暂无评论

Faster algorithms and a smaller kernel for CLIQUES OR TREES VERTEX DELETION

引用

INFORMATION PROCESSING LETTERS 2025年 190卷

作者： Tsur, Dekel Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

In the CLIQUES OR TREES VERTEX DELETION problem, the input is a graph and an integer , and the goal is to decide whether there is a set of at most vertices whose removal from result in a graph in which every connected component is either a clique or a tree. In this paper we give an *(3.46)-time deterministic algorithm, an *(3.103)-time randomized algorithm, and a kernel with (4) vertices for CLIQUES OR TREES VERTEX DELETION.

关键词： Graph algorithms Parameterized complexity branching algorithms Kernelization

来源：评论

学校读者我要写书评

暂无评论

A Refined branching Algorithm for the Maximum Satisfiability Problem

引用

ALGORITHMICA 2022年第4期84卷 982-1006页

作者： Li, Wenjun Xu, Chao Yang, Yongjie Chen, Jianer Wang, Jianxin Changsha Univ Sci & Technol Hunan Prov Key Lab Intelligent Proc Big Data Tran Changsha Peoples R China Saarland Univ Fac Human & Business Sci Chair Econ Theory Saarbrucken Germany Texas A&M Univ Dept Comp Sci & Engn College Stn TX USA Cent South Univ Sch Comp Sci & Engn Changsha Peoples R China

The MAXIMUM SATISFIABILITY problem (MAXSAT) is a fundamental NP-hard problem which has significant applications in many areas. Based on refined observations, we derive a branching algorithm of running time O*(1.2989(m)) for the MAXSAT problem, where m denotes the number of clauses in the given CNF formula. Our algorithm considerably improves the previous best result O*(1.3248(m)) published in 2004. For our purpose, we derive improved branching strategies for variables of degrees 3, 4, and 5. The worst case of our branching algorithm is at certain degree-4 variables. To serve the branching rules, we also propose a variety of reduction rules which can be exhaustively applied in polynomial time.

关键词： Maximum satisfiability branching algorithms Exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Faster parameterized algorithms for variants of 3-Hitting Set

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2025年第4期49卷 1-14页

作者： Tsur, Dekel Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

In the A-Multi3-Hitting Set problem (A-M3HS), where A subset of{1,2,3}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A \subseteq \{1,2,3\}$$\end{document}, the input is a hypergraph G in which the hyperedges have sizes at most 3 and an integer k, and the goal is to decide if there is a set S of at most k vertices such that |S boolean AND e|is an element of A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|S \cap e| \in A$$\end{document} for every hyperedge e. In this paper we give O & lowast;(2.027k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O<^>*(2.027<^>k)$$\end{document}-time algorithms for {1}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{1\}$$\end{document}-M3HS and {1,3}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{1,3\}$$\end{document}-M3HS, and an O & lowast;(1.381k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O<^>*(1.381<^>k)$$\end{document}-time algorithm for {2}\docume

关键词： Graph algorithms Parameterized complexity branching algorithms

来源：评论

学校读者我要写书评

暂无评论

Faster Graph Coloring in Polynomial Space

引用

ALGORITHMICA 2023年第2期85卷 584-609页

作者： Gaspers, Serge Lee, Edward J. UNSW Sydney Sydney NSW Australia

We present a polynomial-space algorithm that computes the number of independent sets of any input graph in time O(1.1389(n)) for graphs with maximum degree 3 and in time O(1.2356(n)) for general graphs, where n is the number of vertices in the input graph. Together with the inclusion-exclusion approach of Bjorklund, Husfeldt, and Koivisto [SIAM J. Comput. 2009], this leads to a faster polynomial-space algorithm for the graph coloring problem with running time O(2.2356(n)) as well as an exponential-space O(1.2330(n)) time algorithm for counting independent sets. Our main algorithm counts independent sets in graphs with maximum degree at most 3 and no vertex with three neighbors of degree 3. This polynomial-space algorithm is designed and analyzed using the recently introduced Separate, Measure and Conquer approach [Gaspers & Sorkin, ICALP 2015]. Using Wahlstrom's compound measure approach, this improvement in running time for small degree graphs is then bootstrapped to larger degrees, giving the improvement for general graphs. Combining both approaches leads to some inflexibility in choosing vertices to branch on for the small-degree cases, which we counter by structural graph properties.

关键词： Graph coloring Exponential time algorithms Analysis of algorithms branching algorithms Counting independent sets

来源：评论

学校读者我要写书评

暂无评论

Faster deterministic algorithms for CO-PATH PACKING and CO-PATH/CYCLE PACKING

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第5期44卷 3701-3710页

作者： Tsur, Dekel Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

In the CO-PATH PACKING (resp., CO-PATH/CYCLE PACKING) problem, the input is a graph G and an integer k, and the goal is to decide whether there is a set of at most k vertices whose removal from G results in a graph which is a collection of induced paths (resp., induced paths and cycles). In this paper we give deterministic O* (3(k))-time algorithms for CO-PATH PACKING and CO-PATH/CYCLE PACKING.

关键词： Graph algorithms Parameterized complexity branching algorithms

来源：评论

学校读者我要写书评

暂无评论

Faster algorithm for pathwidth one vertex deletion

引用

THEORETICAL COMPUTER SCIENCE 2022年 921卷 63-74页

作者： Tsur, Dekel Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

In the PATHWIDTH ONE VERTEX DELETION (POVD) problem the input is a graph G and an integer k, and the goal is to decide whether there is a set of at most k vertices whose removal from G results in a graph with pathwidth at most 1. In this paper we give an algorithm for POVD whose running time is O* (3.888(k)). (c) 2022 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Parameterized complexity branching algorithms

来源：评论

学校读者我要写书评

暂无评论

Faster deterministic algorithm for Co-Path Set

引用

INFORMATION PROCESSING LETTERS 2023年 180卷

作者： Tsur, Dekel Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

In the CO-PATH SET problem, the input is a graph G and an integer k, and the goal is to decide whether there is a set of at most k edges whose removal from G results in a graph in which every connected component is a path. In this paper we give a deterministic O*(2k)-time algorithm for CO-PATH SET.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Parameterized complexity branching algorithms

来源：评论

学校读者我要写书评

暂无评论

Faster parameterized algorithms for BICLUSTER EDITING and FLIP CONSENSUS TREE

引用

THEORETICAL COMPUTER SCIENCE 2023年 953卷

作者： Tsur, Dekel Ben Gurion Univ Negev Beer Sheva Israel

In the BICLUSTER EDITING (resp., FLIP CONSENSUS TREE) problem the input is a bipartite graph G = (V1, V2, E) and an integer k, and the goal is to decide whether there is a set F c V1 X V2 such that the graph (V1, V2, EAF) does not contain an induced path on four vertices (resp., an induced path on five vertices whose endpoints are in V2). In this paper we give algorithms for BICLUSTER EDITING and FLIP CONSENSUS TREE whose running times are O *(2.22k) and O(3.24k), respectively. This improves over the O *(2.636k)-time algorithm for BICLUSTER EDITING of Tsur [IPL 2021] and the O*(3.68k)-time algorithm for FLIP CONSENSUS TREE of Komusiewicz and Uhlmann [Algorithmica 2014].(c) 2023 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Parameterized complexity branching algorithms

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：