Maximum independent set for intervals by divide and conquer with pruning

DOI10.1002/NET.20150MaRDI QIDQ3428912zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Jack Snoeyink

Publication date 30 March 2007

Published in Networks (Search for Journal in Brave)

Full work available at URL https://cdr.lib.unc.edu/downloads/2227mz938

zbMATH Keywords

interval graphoutput-sensitive algorithm

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Algorithms for maximum independent sets
• Irredundant intervals
• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• Algorithm Theory - SWAT 2004

Cited in

(7)

• The two-center problem of uncertain points on a real line
• New properties of maximum independent set problem solution truncation rules or redundant branches
• Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals
• One-dimensional \(k\)-center on uncertain data
• Targeted Branching for the Maximum Independent Set Problem
• Approximation of MWIS on geometric intersection graphs
• (Multivariate) k-SUM as barrier to succinct computation

This page was built for publication: Maximum independent set for intervals by divide and conquer with pruning

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