Exact Algorithms for Maximum Independent Set

DOI10.1007/978-3-642-45030-3_31zbMATH Open1406.68047OpenAlexW2962728077MaRDI QIDQ2872097FDOQ2872097

Mingyu Xiao, Hiroshi Nagamochi

Publication date: 14 January 2014

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-45030-3_31

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cited In (23)

• An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs
• On the Equivalence among Problems of Bounded Width
• Exact exponential algorithms for 3-machine flowshop scheduling problems
• A refined algorithm for maximum independent set in degree-4 graphs
• Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs
• A Polynomial-Space Exact Algorithm for TSP in Degree-6 Graphs
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• An improved exact algorithm for undirected feedback vertex set
• An exact algorithm for maximum independent set in degree-5 graphs
• A fine-grained analysis of a simple independent set algorithm
• Listing Maximal Independent Sets with Minimal Space and Bounded Delay
• On the Complexity Landscape of the Domination Chain
• When polynomial approximation meets exact computation
• Targeted Branching for the Maximum Independent Set Problem
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• When polynomial approximation meets exact computation
• Exact algorithms for maximum independent set
• Large Induced Subgraphs via Triangulations and CMSO
• Faster exact algorithms for some terminal set problems
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• A new decomposition technique for maximal clique enumeration for sparse graphs
• The generalized independent set problem: polyhedral analysis and solution approaches
• Finding near-optimal independent sets at scale

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• GreedyMAX-type Algorithms for the Maximum Independent Set Problem 👍 👎
• Fast algorithms for max independent set 👍 👎
• Efficient exact algorithms through enumerating maximal independent sets and other techniques 👍 👎
• Algorithms for maximum independent sets 👍 👎
• Extending the MAX algorithm for maximum independent set 👍 👎
• A Bottom-Up Method and Fast Algorithms for max independent set 👍 👎
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem 👍 👎
• Exact algorithms for maximum independent set 👍 👎

This page was built for publication: Exact Algorithms for Maximum Independent Set

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