exit

Mathématiques   > Accueil   > Avancées en Mathématiques Pures et Appliquées   > Numéro 1 (Janvier 2023)   > Article

Ensemble de Hitting avec contraintes et arbres de Steiner dans les graphes libres de type SCk et 2K2

Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs


S.Dhanalakshmi
Indian Institute of Information Technology
India

N.Sadagopan
Indian Institute of Information Technology
India



Publié le 13 janvier 2023   DOI : 10.21494/ISTE.OP.2023.0903

Résumé

Abstract

Mots-clés

Keywords

Strictly Chordality-k graphs (SCk) are graphs which are either cycle-free or every induced cycle is of length exactly $$${k, k \geq 3}$$$. Strictly chordality-3 and strictly chordality-4 graphs are well known chordal and chordal bipartite graphs, respectively. For $$${k \geq 5}$$$, the study has been recently initiated in [1] and various structural and algorithmic results are reported. In this paper, we study SCk graphs in the algorithmic front and the study concerns the class of graphs where $$${k \geq 5}$$$. We show that recognizing vertex cycle ordering (VCO) for SCk, $$${k \geq 5}$$$ graphs, maximum independent set (MIS), minimum vertex cover, minimum dominating set, feedback vertex set (FVS), odd cycle transversal (OCT), even cycle transversal (ECT) and Steiner tree problem are linear time solvable on SCk graphs, $$${k \geq 5}$$$. We next consider 2K2-free graphs and discussed the algorithmic problems such as FVS, OCT, ECT and Steiner tree problem on the subclasses of 2K2-free graphs.

Strictly Chordality-k graphs (SCk) are graphs which are either cycle-free or every induced cycle is of length exactly $$${k, k \geq 3}$$$. Strictly chordality-3 and strictly chordality-4 graphs are well known chordal and chordal bipartite graphs, respectively. For $$${k \geq 5}$$$, the study has been recently initiated in [1] and various structural and algorithmic results are reported. In this paper, we study SCk graphs in the algorithmic front and the study concerns the class of graphs where $$${k \geq 5}$$$. We show that recognizing vertex cycle ordering (VCO) for SCk, $$${k \geq 5}$$$ graphs, maximum independent set (MIS), minimum vertex cover, minimum dominating set, feedback vertex set (FVS), odd cycle transversal (OCT), even cycle transversal (ECT) and Steiner tree problem are linear time solvable on SCk graphs, $$${k \geq 5}$$$. We next consider 2K2-free graphs and discussed the algorithmic problems such as FVS, OCT, ECT and Steiner tree problem on the subclasses of 2K2-free graphs.

Strictly Chordality-k graphs 2K2-free graphs Feedback Vertex Set Odd (Even) Cycle Transversal Steiner tree

Strictly Chordality-k graphs 2K2-free graphs Feedback Vertex Set Odd (Even) Cycle Transversal Steiner tree