Search

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 u w 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 + u w , 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 + u w , i.e., the minimum number of non-edges (excluding the tail u w ) to be added to G + u w so that the resulting graph belongs to C. In this paper, we study this problem for the classes of split, quasi-threshold, threshold and P 4 -sparse graphs and we present linear-time algorithms by exploiting the structure of split graphs and the tree representation of quasi-threshold, threshold and P 4 -sparse graphs. [ABSTRACT FROM AUTHOR]

Software watermarking is a defense technique used to prevent or discourage software piracy by embedding a signature in the code. In (Discrete Applied Mathematics250 (2018) 145–164), a software watermarking system is presented which encodes an integer number w (i.e., a watermark) as a reducible permutation flow-graph F [ π ∗ ] embeddable in the code through the use of a self-inverting permutation π ∗ . In this work, we theoretically investigate this watermarking system and exploit structural properties of the self-inverting permutation π ∗ encoding the watermark in order to prove its resilience to edge-modification attacks on the flow-graph F [ π ∗ ]. Based on the minimum number of edge modifications needed to be applied on F [ π ∗ ] so that a different watermark can be extracted from the resulting graph, we give a characterization of the watermarks as strong, intermediate or weak and provide good recommendations for the choices of watermark. [ABSTRACT FROM AUTHOR]

In this paper we present a graph-based framework that, utilizing relations between groups of System-calls, detects whether an unknown software sample is malicious or benign, and classifies a malicious software to one of a set of known malware families. In our approach we propose a novel graph representation of dependency graphs by capturing their structural evolution over time constructing sequential graph instances, the so-called Temporal Graphs. The partitions of the temporal evolution of a graph defined by specific time-slots, results to different types of graphs representations based upon the information we capture across the capturing of its evolution. The proposed graph-based framework utilizes the proposed types of temporal graphs computing similarity metrics over various graph characteristics in order to conduct the malware detection and classification procedures. Finally, we evaluate the detection rates and the classification ability of our proposed graph-based framework conducting a series of experiments over a set of known malware samples pre-classified into malware families. [ABSTRACT FROM AUTHOR]

Abstract: Nakano et al. [A time-optimal solution for the path cover problem on cographs, Theoret. Comput. Science 290 (2003) 1541–1556] presented a time- and work-optimal algorithm for finding the smallest number of vertex-disjoint paths that cover the vertices of a cograph and left open the problem of applying their technique into other classes of graphs. Motivated by this issue we generalize their technique and apply it to the class of -sparse graphs, which forms a proper superclass of cographs. We show that the path cover problem on -sparse graphs can also be optimally solved. More precisely, given a -sparse graph G on n vertices and its modular decomposition tree, we describe an optimal parallel algorithm which returns a minimum path cover of G in time using processors on the EREW PRAM model. Our results generalize previous results and extend the family of perfect graphs admitting optimal solutions for the path cover problem. [Copyright &y& Elsevier]

The Kn-complement of a graph G, denoted by Kn - G, is defined as the graph obtained from the complete graph Kn by removing a set of edges that span G; if G has n vertices, then Kn - G coincides with the complement G̅ of the graph G. In this paper we extend the previous notion and derive determinant based formulas for the number of spanning trees of graphs of the form Knm ± G, where Knm is the complete multigraph on n vertices with exactly m edges joining every pair of vertices and G is a multigraph spanned by a set of edges of Knm; the graph Knm +G (resp. Knm - G) is obtained from Knm by adding (resp. removing) the edges of G. Moreover, we derive determinant based formulas for graphs that result from Knm by adding and removing edges of multigraphs spanned by sets of edges of the graph Knm. We also prove closed formulas for the number of spanning tree of graphs of the form Knm ±G, where G is (i) a complete multipartite graph, and (ii) a multi-star graph. Our results generalize previous results and extend the family of graphs admitting formulas for the number of their spanning trees. [ABSTRACT FROM AUTHOR]

In this paper, we consider the recognition problem on three classes of perfect graphs, namely, the HH-free, the HHD-free, and the Welsh-Powell opposition graphs (or WPO-graphs). In particular, we prove properties of the chordal completion of a graph and show that a modified version of the classic linear-time algorithm for testing for a perfect elimination ordering can be efficiently used to determine in O(n min{mα(n, n), m + n log n}) time whether a given graph G on n vertices and m edges contains a house or a hole; this implies an O(n min{mα(n, n), m + n log n})-time and O(n + m)-space algorithm for recognizing HH-free graphs, and in turn leads to an HHD-free graph recognition algorithm exhibiting the same time and space complexity. We also show that determining whether the complement G̅ of the graph G is HH-free can be efficiently resolved in O(nm) time using O(n²) space, which leads to an O(nm)-time and O(n²)-space algorithm for recognizing WPO-graphs. The previously best algorithms for recognizing HH-free, HHD-free, and WPO-graphs required O(n3) time and O(n2) space. [ABSTRACT FROM AUTHOR]

The Kn-complement of a graph G, denoted by Kn - G, is defined as the graph obtained from the complete graph Kn by removing a set of edges that span G; if G has n vertices, then Kn - G coincides with the complement G̅ of the graph G. In this paper we extend the previous notion and derive determinant based formulas for the number of spanning trees of graphs of the form Knm ± G, where Km n is the complete multigraph on n vertices with exactly m edges joining every pair of vertices and G is a multigraph spanned by a set of edges of K Knm; the graph Knm + G (resp. Knm - G) is obtained from K Knm by adding (resp. removing) the edges of G. Moreover, we derive determinant based formulas for graphs that result from Knm by adding and removing edges of multigraphs spanned by sets of edges of the graph Knm. We also prove closed formulas for the number of spanning tree of graphs of the form Knm ± G, where G is (i) a complete multipartite graph, and (ii) a multi-star graph. Our results generalize previous results and extend the family of graphs admitting formulas for the number of their spanning trees. [ABSTRACT FROM AUTHOR]

In this paper, we consider the recognition problem on three classes of perfect graphs, namely, the HH-free, the HHD-free, and the Welsh-Powell opposition graphs (or WPO-graphs). In particular, we prove properties of the chordal completion of a graph and show that a modified version of the classic linear-time algorithm for testing for a perfect elimination ordering can be efficiently used to determine in O(n min{m α(n, n), m + n log n}) time whether a given graph G on n vertices and m edges contains a house or a hole; this implies an O(n min{m α (n, n), m + n log n})-time and O(n + m)-space algorithm for recognizing HH-free graphs, and in turn leads to an HHD-free graph recognition algorithm exhibiting the same time and space complexity. We also show that determining whether the complement G of the graph G is HH-free can be efficiently resolved in O(nm) time using O(n²) space, which leads to an O(nm)-time and O(n²) space algorithm for recognizing WPO-graphs. The previously best algorithms for recognizing HH-free, HHD-free, and WPO-graphs required O(n³) time and O(n²) space. [ABSTRACT FROM AUTHOR]

In this paper we examine the classes of graphs whoseK n-complements are trees or quasi-threshold graphs and derive formulas for their number of spanning trees; for a subgraphHofK n, theK n-complement ofHis the graphK n-Hwhich is obtained fromK n by removing the edges ofH. Our proofs are based on the complement spanning-tree matrix theorem, which expresses the number of spanning trees of a graph as a function of the determinant of a matrix that can be easily constructed from the adjacency relation of the graph. Our results generalize previous results and extend the family of graphs of the formK n-Hadmitting formulas for the number of their spanning trees. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of computing the connected components of the complement of a given graph. We describe a simple sequential algorithm for this problem, which works on the input graph and not on its complement, and which for a graph on n vertices and m edges runs in optimal O(n+m) time. Moreover, unlike previous linear co-connectivity algorithms, this algorithm admits efficient parallelization, leading to an optimal O(log n)-time and O((n+m)log n)-processor algorithm on the EREW PRAM model of computation. It is worth noting that, for the related problem of computing the connected components of a graph, no optimal deterministic parallel algorithm is currently available. The co-connectivity algorithms find applications in a number of problems. In fact, we also include a parallel recognition algorithm for weakly triangulated graphs, which takes advantage of the parallel co-connectivity algorithm and achieves an O(log2 n) time complexity using O((n+m2) log n) processors on the EREW PRAM model of computation. [ABSTRACT FROM AUTHOR]

We prove algorithmic characterizations of weakly chordal graphs, which lead to efficient parallel algorithms for recognizing P5-free and &Pmacr;5-free weakly chordal graphs. For an input graph on n vertices and m edges, our algorithms run in O(log2 n) time and require O(m2/log n) processors on the EREW PRAM model of computation. The proposed recognition algorithms efficiently detect P5s and &Pmacr;5s in weakly chordal graphs in O(log n) time with O(m2/log n) processors on the EREW PRAM. Additionally, we show how the algorithms can be augmented to provide a certificate for the existence of a P5 (or a &Pmacr;5) in case the input graph is not P5-free (respectively, &Pmacr;5-free) weakly chordal. [ABSTRACT FROM AUTHOR]

In this paper we show structural and algorithmic properties on the class of quasi-threshold graphs, or QT-graphs for short, and prove necessary and sufficient conditions for a QT-graph to be Hamiltonian. Based on these properties and conditions, we construct an efficient parallel algorithm for finding a Hamiltonian cycle in a QT-graph; for an input graph on n vertices and m edges, our algorithm takes O(log n) time and requires O(n+m) processors on the CREW PRAM model. In addition, we show that the problem of recognizing whether a QT-graph is a Hamiltonian graph and the problem of computing the Hamiltonian completion number of a nonHamiltonian QT-graph can also be solved in O(log n) time with O(n+m) processors. Our algorithms rely on O(log n)-time parallel algorithms, which we develop here, for constructing tree representations of a QT-graph; we show that a QT-graph G has a unique tree representation, that is, a tree structure which meets the structural properties of G. We also present parallel algorithms for other optimization problems on QT-graphs which run in O(log n) time using a linear number of processors. [Copyright &y& Elsevier]