Exact Algorithms for Maximum Independent Set

DOI10.1007/978-3-642-45030-3_31MaRDI QIDQ2872097zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Exact algorithms for maximum independent set
• Algorithms for maximum independent sets
• Publication:4864968
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• Fast algorithms for max independent set
• GreedyMAX-type algorithms for the maximum independent set problem
• Extending the MAX algorithm for maximum independent set
• scientific article; zbMATH DE number 637355
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• A bottom-up method and fast algorithms for Max Independent Set

Cited in

(38)

• A polytime preprocess algorithm for the maximum independent set problem
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• A new decomposition technique for maximal clique enumeration for sparse graphs
• When polynomial approximation meets exact computation
• The \(0-1\) inverse maximum independent set problem on forests and unicyclic graphs
• The \textsc{max quasi-independent set} problem
• On the maximum independent set problem in graphs of bounded maximum degree
• A bottom-up method and fast algorithms for Max Independent Set
• A polynomial-space exact algorithm for TSP in degree-6 graphs
• Listing Maximal Independent Sets with Minimal Space and Bounded Delay
• A note on the fine-grained complexity of MIS on regular graphs
• Constructing concrete hard instances of the maximum independent set problem
• Targeted Branching for the Maximum Independent Set Problem
• The generalized independent set problem: polyhedral analysis and solution approaches
• Fast local search for the maximum independent set problem
• On the complexity landscape of the domination chain
• Fast algorithms for max independent set
• Algorithms for maximum independent sets
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• An exact algorithm for maximum independent set in degree-5 graphs
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• Faster exact algorithms for some terminal set problems
• A simple and fast algorithm for Maximum Independent Set in 3-degree graphs (extended abstract)
• Faster computation of the maximum dissociation set and minimum 3-path vertex cover in graphs
• Exact exponential algorithms for 3-machine flowshop scheduling problems
• On sequential heuristic methods for the maximum independent set problem
• When polynomial approximation meets exact computation
• A fine-grained analysis of a simple independent set algorithm
• Maximum independent sets near the upper bound
• An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• On the equivalence among problems of bounded width
• Exact algorithms for maximum independent set
• An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs
• A refined algorithm for maximum independent set in degree-4 graphs
• Large Induced Subgraphs via Triangulations and CMSO
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• An improved exact algorithm for undirected feedback vertex 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)