1-extendability of independent sets

DOI10.1007/s00453-023-01138-8OpenAlexW4380051920MaRDI QIDQ6119830

Pierre Bergé, Anthony Busson, Rémi Watrigant, Carl Feghali

Publication date: 25 March 2024

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-023-01138-8

zbMATH Keywords

independent set1-extendable graphsB-graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• Parameterized complexity of independent set in H-free graphs
• On n-extendable graphs
• Unit disk graphs
• Some simplified NP-complete graph problems
• Well-covered graphs and extendability
• Extending matchings in graphs: A survey
• The matching extension problem in general graphs is co-NP-complete
• Face covers and the genus problem for apex graphs
• Well-covered claw-free graphs
• Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs
• Optimal Binary Space Partitions in the Plane
• Universality considerations in VLSI circuits
• Complexity results for well‐covered graphs
• Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs
• Parameterized Algorithms
• Some covering concepts in graphs
• On the complexity of \(k\)-SAT
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: 1-extendability of independent sets