Exact algorithms for maximum independent set
type: Item
instance of: scholarly article
title: Exact algorithms for maximum independent set
zbMATH Open document ID: 1371.68126
author: Mingyu Xiao
author: Hiroshi Nagamochi
published in: Information and Computation
publication date: 2017-08-08T00:00:00Z
full work available at URL: https://arxiv.org/abs/1312.6260
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6758667
zbMATH Keywords: exact algorithm
zbMATH Keywords: independent set
zbMATH Keywords: graph
zbMATH Keywords: polynomial-space
zbMATH Keywords: branch-and-reduce
zbMATH Keywords: measure-and-conquer
zbMATH Keywords: amortized analysis
MaRDI profile type: Publication
OpenAlex ID: W1518653692
Wikidata QID: Q56335614
arXiv ID: 1312.6260
cites work: Q4252376
cites work: Fast algorithms for max independent set
cites work: Vertex cover: Further observations and further improvements
cites work: Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
cites work: A measure & conquer approach for the analysis of exact algorithms
cites work: Exact exponential algorithms.
cites work: A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs
cites work: An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
cites work: A fine-grained analysis of a simple independent set algorithm
cites work: An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
cites work: Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
cites work: Algorithms for maximum independent sets
cites work: Finding a Maximum Independent Set
cites work: A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
cites work: Q4869540
cites work: Q4414647
cites work: A Simple and Fast Algorithm for Maximum Independent Set in 3-Degree Graphs
cites work: Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
cites work: A refined algorithm for maximum independent set in degree-4 graphs
cites work: An exact algorithm for maximum independent set in degree-5 graphs
cites work: Exact Algorithms for Maximum Independent Set
DOI: 10.1016/J.IC.2017.06.001
DBLP publication ID: journals/iandc/XiaoN17
description: scientific article