Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract)

DOI10.1007/978-3-030-89543-3_51OpenAlexW3211025827MaRDI QIDQ2695332

Sen Huang, Mingyu Xiao, Xiao-yu Chen

Publication date: 30 March 2023

Full work available at URL: https://arxiv.org/abs/2108.12840

zbMATH Keywords

graph algorithmsexact algorithmsmeasure-and-conquerreduction rulesmaximum weighted independent set

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• On two techniques of combining branching and treewidth
• Counting models for 2SAT and 3SAT formulae
• Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
• Exact algorithms for maximum independent set
• Fast algorithms for max independent set
• Approximation algorithms on consistent dynamic map labeling
• Vertex Cover: Further Observations and Further Improvements
• A Fine-grained Analysis of a Simple Independent Set Algorithm
• A measure & conquer approach for the analysis of exact algorithms
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• Algorithms for maximum independent sets
• Finding a Maximum Independent Set
• Reducibility among Combinatorial Problems
• Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs
• Algorithms for Counting 2-Sat Solutions and Colorings with Applications
• Branching and Treewidth Based Exact Algorithms