S. M. Dhannya ; N. S. Narayanaswamy ; K. K. Nisha - Exactly Hittable Interval Graphs

dmtcs:10762 - Discrete Mathematics & Theoretical Computer Science, November 30, 2023, vol. 25:3 special issue ICGT'22 - https://doi.org/10.46298/dmtcs.10762
Exactly Hittable Interval GraphsArticle

Authors: S. M. Dhannya ; N. S. Narayanaswamy ; K. K. Nisha

    Given a set system $\mathcal{X} = \{\mathcal{U},\mathcal{S}\}$, where $\mathcal{U}$ is a set of elements and $\mathcal{S}$ is a set of subsets of $\mathcal{U}$, an exact hitting set $\mathcal{U}'$ is a subset of $\mathcal{U}$ such that each subset in $\mathcal{S}$ contains exactly one element in $\mathcal{U}'$. We refer to a set system as exactly hittable if it has an exact hitting set. In this paper, we study interval graphs which have intersection models that are exactly hittable. We refer to these interval graphs as exactly hittable interval graphs (EHIG). We present a forbidden structure characterization for EHIG. We also show that the class of proper interval graphs is a strict subclass of EHIG. Finally, we give an algorithm that runs in polynomial time to recognize graphs belonging to the class of EHIG.


    Volume: vol. 25:3 special issue ICGT'22
    Section: Special issues
    Published on: November 30, 2023
    Accepted on: October 31, 2023
    Submitted on: January 3, 2023
    Keywords: Computer Science - Data Structures and Algorithms

    Consultation statistics

    This page has been seen 547 times.
    This article's PDF has been downloaded 411 times.