An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs

DOI10.1007/978-3-642-38756-2_10MaRDI QIDQ5405918zbMATH OpenOpenAlexFDO

Authors Mingyu Xiao, Hiroshi Nagamochi

Publication date 3 April 2014

Published in Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-38756-2_10

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• An exact algorithm for maximum independent set in degree-5 graphs
• On maximum independent sets in \(P_{5}\)-free graphs
• A randomized algorithm for determining dominating sets in graphs of maximum degree five
• An optimal maximal independent set algorithm for bounded-independence graphs
• Maximum independent sets in subclasses of \(P_{5}\)-free graphs
• Exact algorithms for maximum independent set
• Exact Algorithms for Maximum Independent Set
• A refined algorithm for maximum independent set in degree-4 graphs
• A simple and fast algorithm for Maximum Independent Set in 3-degree graphs (extended abstract)
• On the maximum independent set problem in graphs of bounded maximum degree

Cited in

(8)

• A randomized algorithm for determining dominating sets in graphs of maximum degree five
• A refined algorithm for maximum independent set in degree-4 graphs
• Exact algorithms for maximum independent set
• An improved exact algorithm for TSP in graphs of maximum degree 4
• scientific article; zbMATH DE number 861311 (Why is no real title available?)
• Exact and Parameterized Algorithms for the Independent Cutset Problem
• Exact and parameterized algorithms for the independent cutset problem
• An exact algorithm for maximum independent set in degree-5 graphs

This page was built for publication: An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5405918)