Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 18 of 18 for “"SPLIT GRAPHS"”.
-
Encoding graphs by words and morphisms
This thesis is related to encoding graphs by words, where we deal with so called word representation of graphs, relevant to them semi-transitive orientations, and more exotic ways to represent graphs via bijections with certain words and pattern-avoiding permutations.In Chapter 2, we introduce a …
-
Exact and Factor Two Algorithms for Broadcast Time
… begin by studying the broadcast time problem on split graphs. First, we introduce a tight polynomial-time constant approximation algorithm for broadcasting on split graphs. Then, we study some important characteristics of an optimal broadcast scheme on split graphs and design a strategy for …
-
Broadcast independence and broadcast packing
… two broadcast parameters in different classes of graphs. Determining the broadcast independence number is NP-hard for planar graphs of maximum degree 4, and before this thesis, the best known algorithm to compute the broadcast independence number of a tree of order n had time complexity O(n^9), …
-
Sampling of Random Graphs with Prescribed Degree Sequence
… information, one must sample the ensemble of graphs that satisfy the constraint of the known structure, but are otherwise as random as possible. Similar to the microcanonical ensemble and canonical ensemble in statistical physics, there are two types of methods to generate an ensemble of …
-
On Induced Subgraphs, Degree Sequences, and Graph Structure
… equivalent characterizations of the class of A4-split graphs, those having the same A4-structure as some split graph.
-
Algorithms and complexity of graph modification problems
… was recently shown to be NP-complete for general graphs. Here we initiate the study of graph classes for which MaxSTC is solvable in polynomial time or NP-complete. On the positive side, we show that the problem admits a polynomial-time algorithm for the following incomparable classes of graphs: …
-
Lower Bounds and Algorithms for Searching Networks
… and extend the results to a broader class of graphs including toroidal grids. In addition, we examine the complete k-partite graphs and provide lower bounds and upper bounds on their fast search number. We also investigate some special classes of complete k-partite graphs, such as complete …
-
A New Optimality Measure for Distance Dominating Sets
… two even when the input graph is restricted to split graphs, <em>2</em>-connected graphs, or planar bipartite graphs of degree four. In addition, the problem is in P for bounded tree-width graphs, when considering <em>k</em> as a constant, and for strongly chordal graphs, for any <em>k</em>. …
-
On End Vertices of Search Algorithms
… problem, we show it is NP-complete on bipartite graphs as well as degree restricted bipartite graphs for Lexicographic Breadth First Search, but solvable in polynomial time on split graphs for Breadth First Search. We show that the end-vertex problem is tractable for Lexicographic Breadth First …
-
Essays on Network formation games
… friends. As a result, We present that nested split graphs are drawn from survey data because researchers tend to ask respondents to list only a few friends.
-
Combinatorial Generalizations of Sieve Methods and Characterizing Hamiltonicity via Induced Subgraphs
… the combinatorial Turán sieve to count labelled graphs and we apply the combinatorial Selberg sieve to count subspaces of finite spaces. Finding sufficient conditions for Hamiltonicity in graphs is a classical topic, where the difficulty is bracketed by the NP-hardness of the associated decision …
-
On (in)tractability of connection and cut problems
… restricted to specific graph classes, such as split graphs, rooted directed path graphs, and graphs of bounded clique-width. We mainly concentrate on results that differentiate the complexity of TCP from the complexity of Steiner tree. Additionally, we analyse the computational complexity of …
-
On the Complexity of Reconfiguration of Clique, Cluster Vertex Deletion, and Dominating Set
… linear-time solvable for paths, trees, bipartite graphs, chordal graphs, and cographs. Then, we prove that the Cluster Vertex Deletion Reconfiguration problem is linear-time solvable for paths and trees, and that it is NP-hard on bipartite graphs, and PSPACE-complete in general. Finally, we …
-
Edge modification on perfect and reducible graphs with application to watermarking
… to edge modification problems on classes of graphs. For the theoretical part, we study and present polynomial algorithms for the minimum completion problem (i) of a graph with a “tail” for four subclasses of perfect graphs and (ii) of a graph and an added edge for the class of P4-sparse …
-
Modularity in Biological Networks
… that are not fully partitionable as a union of split graphs, and posed the problem of finding modules and transition regions as a graph editing problem, proving its hardness and providing exact algorithms and heuristics. The discussion of each of the two tasks is completed by an example of a …
-
Energia laplaciana sem sinal de grafos
… dentre todos os grafos com n v ertices e o grafo split completo com uma clique de [n+1/ 3] v ertices e provamos tal conjectura para algumas classes de grafos, em particular, para arvores, grafos unic clicos e bic clicos.
-
Large-Scale Optimization Models with Applications in Biological and Emergency Response Networks
… remains NP-complete for both bipartite and split graphs. In addition, we propose a decomposition framework which is suitable for both the existing and the new formulations. We implement several acceleration techniques in this framework, motivated by those techniques used in Benders …
-
ΠΑΡΑΛΛΗΛΟΙ ΑΛΓΟΡΙΘΜΟΙ ΓΙΑ ΠΡΟΒΛΗΜΑΤΑ ΤΕΛΕΙΩΝ ΓΡΑΦΗΜΑΤΩΝ
… PROBLEMS, PARTICULARLY FOR PROBLEMS ON PERFECT GRAPHS. ALL ALGORITHMSARE BASED ON A NEW PRESENTATION OF THE UNDIRECTED GRAPHS. THE VERTEX SET V OF A GRAPH G=(V,E) IS PARTITIONED INTO SUBSETS, IN A SPECIFIC FASHION. WE CALL THESE SUBSETS "ADJACENCY LEVEL SETS" AND DENOTE AL(V,L), VEV, 0<L< V . …