Exact Algorithms for Maximum Independent Set
From MaRDI portal
Publication:2872097
DOI10.1007/978-3-642-45030-3_31zbMath1406.68047OpenAlexW2962728077MaRDI QIDQ2872097
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
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (19)
Faster exact algorithms for some terminal set problems ⋮ Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs ⋮ On the Equivalence among Problems of Bounded Width ⋮ Finding near-optimal independent sets at scale ⋮ A refined algorithm for maximum independent set in degree-4 graphs ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ An exact algorithm for maximum independent set in degree-5 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 ⋮ When polynomial approximation meets exact computation ⋮ 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 ⋮ Exact exponential algorithms for 3-machine flowshop scheduling problems ⋮ Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems ⋮ When polynomial approximation meets exact computation ⋮ The generalized independent set problem: polyhedral analysis and solution approaches ⋮ Exact algorithms for maximum independent set ⋮ On the Complexity Landscape of the Domination Chain ⋮ An improved exact algorithm for undirected feedback vertex set
This page was built for publication: Exact Algorithms for Maximum Independent Set