MyJournals Home  

RSS FeedsAlgorithms, Vol. 16, Pages 289: Adding a Tail in Classes of Perfect Graphs (Algorithms)


3 june 2023 10:23:17

Algorithms, Vol. 16, Pages 289: Adding a Tail in Classes of Perfect Graphs (Algorithms)

Consider a graph G which belongs to a graph class C. We are interested in connecting a node w∉V(G) to G by a single edge uw where u∈V(G); we call such an edge a tail. As the graph resulting from G after the addition of the tail, denoted G+uw, need not belong to the class C, we want to compute the number of non-edges of G in a minimum C-completion of G+uw, i.e., the minimum number of non-edges (excluding the tail uw) to be added to G+uw so that the resulting graph belongs to C. In this paper, we study this problem for the classes of split, quasi-threshold, threshold and P4-sparse graphs and we present linear-time algorithms by exploiting the structure of split graphs and the tree representation of quasi-threshold, threshold and P4-sparse graphs.

48 viewsCategory: Informatics
Algorithms, Vol. 16, Pages 288: An Adaptive Deep Learning Neural Network Model to Enhance Machine-Learning-Based Classifiers for Intrusion Detection in Smart Grids (Algorithms)
Algorithms, Vol. 16, Pages 290: Integration of Polynomials Times Double Step Function in Quadrilateral Domains for XFEM Analysis (Algorithms)
blog comments powered by Disqus
The latest issues of all your favorite science journals on one page


Register | Retrieve



Copyright © 2008 - 2023 Indigonet Services B.V.. Contact: Tim Hulsen. Read here our privacy notice.
Other websites of Indigonet Services B.V.: Nieuws Vacatures News Tweets Nachrichten