Minimal Hitting-Sets: Concepts and Algorithms

Erscheinungsjahr 2026
ISBN: 978-981-9265-79-4
Verlag: Springer

Buch, Englisch, 117 Seiten, Format (B × H): 155 mm x 235 mm

This open access monograph offers a comprehensive, up-to-date, and self-contained account of the authors' in-depth research on minimal hitting-sets (MHSs) for model-based fault diagnosis. The task of deriving all MHSs from conflict sets is a classic NP-hard problem in computer science, and this book systematically presents a suite of efficient algorithms designed to tackle it—serving as an essential reference for researchers, engineers, and students confronting related NP-hard challenges.

The work is distinguished by its unique threefold conceptualization of minimal hitting-sets, developed independently within the frameworks of set theory, logic theory, and graph theory. Alongside these theoretical foundations, the book provides a thorough exposition of centralized algorithms, distributed strategies, and divide-and-conquer-based approaches for the efficient generation of all MHSs. Crucially, it demonstrates how the inherent complexity can be substantially reduced—from O(2^) to O(2^(/)), or from quadratic to linear time—by leveraging distributed schemes and divide-and-conquer methods that exploit special structural properties, leading to significant improvements in runtime performance.

Readers will acquire a solid, multi-perspective understanding of the MHS concept and gain hands-on familiarity with representative efficient algorithms. Assuming only a basic prerequisite knowledge of set, logic, and graph theories, this book is ideally suited for researchers, professionals, and graduate students in computer science and related fields.

Zielgruppe

Research

Autoren/Hrsg.

Zhao, Xiangfu

Ouyang, Dantong

Fachgebiete

• Mathematik | Informatik EDV | Informatik Informatik Künstliche Intelligenz
• Mathematik | Informatik EDV | Informatik Informatik Mathematik für Informatiker

Inhaltsverzeichnis

Chapter 1. Introduction.- Chapter 2. Representation of MHS.- Chapter 3. Centralized Algorithms.- Chapter 4. Distributed Strategies.- Chapter 5. Divide-and-Conquer Based Strategies.- Chapter 6. RelatedWork and Discussion.- Chapter 7. Conclusion and Perspectives.

Über Autor(innen)

Xiangfu Zhao received his Ph.D. degree in computer science at Jilin University, Changchun, Jilin, China, in 2009. He was a visiting professor in Italy from August 2012 to July 2013. Currently, he is a professor at Yantai University, Yantai, Shandong, China. His research interests include model-based diagnostic reasoning (e.g., algorithms for deriving minimal hitting sets) and blockchain technology. Currently, he is an executive member of the China Computer Federation (CCF) Blockchain Committee and Theorical Computer Science Committee. To date, he has published more than 70 scholarly papers. He is the PI of two NSFC projects. He was invited to serve as the IJCAI-19 Session Chair, a PC member of AAAI-15/18/21/22/24 and IJCAI-19/20.

Dantong Ouyang received her Ph.D. degree in computer science at Jilin University, Changchun, Jilin, China, in 1998. Now, she is a professor at Jilin University, Changchun, Jilin, China. Her research interests include model-based diagnostic reasoning,the semantic web, and model checking. Currently, she is an executive member of the China Computer Federation (CCF) AI committees and Theorical Computer Science committees. To date, she has published more than 150 scholarly papers. She is a PI of four NSFC projects. She was invited to serve as a PC chair/member of many outstanding conferences.