A polytime preprocess algorithm for the maximum independent set problem
From MaRDI portal
Publication:6151535
DOI10.1007/s11590-023-02076-8MaRDI QIDQ6151535
Samuel Kroger, Illya V. Hicks, Hamidreza Validi
Publication date: 11 March 2024
Published in: Optimization Letters (Search for Journal in Brave)
Cites Work
- Unnamed Item
- Unnamed Item
- Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs
- On maximal independent sets of vertices in claw-free graphs
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Geometric algorithms and combinatorial optimization
- A \(2k\)-kernelization algorithm for vertex cover based on crown decomposition
- Using critical sets to solve the maximum independent set problem
- The stable set problem and the thinness of a graph
- Vertices Belonging to All or to No Maximum Stable Sets of a Graph
- Vertex packings: Structural properties and algorithms
- Nondeterminism within $P^ * $
- A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
- Solving the Distance-Based Critical Node Problem
- Why Is Maximum Clique Often Easy in Practice?
- Independent Set in P5-Free Graphs in Polynomial Time
- Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
This page was built for publication: A polytime preprocess algorithm for the maximum independent set problem