Minimum consistent subset in trees and interval graphs

DOI10.4230/LIPICS.FSTTCS.2024.7MaRDI QIDQ7263564zbMATH OpenFDO

Authors Aritra Banik, Sayani Das, Anil Maheshwari, Bubai Manna, Subhas C. Nandy, Krishna Priya Priya K. M., Bodhayan Roy, Sasanka Roy, Abhishek Sahu

Publication date 12 June 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2024.7

zbMATH Keywords

\textsf{NP}-completeinterval graphsminimum consistent subsetnearest-neighbor classificationparameterized complexitytrees

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites work

• Algorithms and hardness results for nearest neighbor problems in bicolored point sets
• Consistent subset problem with two labels
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• Minimum consistent subset of simple graph classes
• Minimum consistent subset problem for trees
• On the minimum consistent subset problem
• Parameterized algorithms
• Refined lower bounds for nearest neighbor condensation
• Some simplified NP-complete graph problems
• The minimum consistent spanning subset problem on trees

This page was built for publication: Minimum consistent subset in trees and interval graphs

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