Exact Algorithms for Maximum Independent Set

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

Mathematics Subject Classification ID

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