An $O^*(1.0821^n)$-Time Algorithm for Computing Maximum Independent Set in Graphs with Bounded Degree 3

Davis Issac; Ragesh Jaiswal

An $O^*(1.0821^n)$-Time Algorithm for Computing Maximum Independent Set in Graphs with Bounded Degree 3

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1308.1351 v4 pith:W7PRK4D5 submitted 2013-08-06 cs.DS

Davis Issac , Ragesh Jaiswal This is my paper · ORCID

classification cs.DS

keywords timealgorithmboundedcomputingdegreegraphsindependentmaximum

verification ladder T0 review T1 audit T2 compute T3 formal

0 comments

abstract

We give an $O^*(1.0821^n)$-time, polynomial space algorithm for computing Maximum Independent Set in graphs with bounded degree 3. This improves all the previous running time bounds known for the problem.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Automated Discovery of Branching Rules with Optimal Complexity for the Maximum Independent Set Problem
math.OC 2024-12 conditional novelty 8.0 of 10

A set-cover based method automatically generates provably (locally) optimal branching rules for the maximum independent set problem, improving empirical average branching factors on 3-regular graphs.

Pith tools