Maximum Weighted Independent Set: Effective Reductions and Fast Algorithms on Sparse Graphs

DOI10.1007/S00453-023-01197-XMaRDI QIDQ6492080zbMATH OpenFDO

Authors Mingyu Xiao, Sen Huang

Publication date 24 April 2024

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00453-023-01197-X

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Cites work

• A fine-grained analysis of a simple independent set algorithm
• A measure \& conquer approach for the analysis of exact algorithms
• A multivariate framework for weighted FPT algorithms
• A refined algorithm for maximum independent set in degree-4 graphs
• A simple and fast algorithm for Maximum Independent Set in 3-degree graphs (extended abstract)
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• Algorithms for Counting 2-Sat Solutions and Colorings with Applications
• Algorithms for maximum independent sets
• An exact algorithm for maximum independent set in degree-5 graphs
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs
• Approximation algorithms on consistent dynamic map labeling
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• Branching and Treewidth Based Exact Algorithms
• Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
• Counting models for 2SAT and 3SAT formulae
• Exact algorithms for maximum independent set
• Exact exponential algorithms.
• Exactly solving the maximum weight independent set problem on large real-world graphs
• Fast algorithms for max independent set
• Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
• Finding a Maximum Independent Set
• scientific article; zbMATH DE number 1305487 (Why is no real title available?)
• scientific article; zbMATH DE number 2119675 (Why is no real title available?)
• Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
• Linear-time modular decomposition of directed graphs
• On efficient fixed-parameter algorithms for weighted vertex cover
• On two techniques of combining branching and treewidth
• Reducibility among combinatorial problems
• Vertex cover: Further observations and further improvements

Cited in

(1)

• Finding near-optimal weight independent sets at scale

This page was built for publication: Maximum Weighted Independent Set: Effective Reductions and Fast Algorithms on Sparse Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6492080)