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"”.

  1. 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 …

    strathclyde Repository record for Encoding graphs by words and morphisms (opens in a new tab)

  2. 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 …

    concordia Download PDF for Exact and Factor Two Algorithms for Broadcast Time (opens in a new tab)

  3. 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), …

    uvic Repository record for Broadcast independence and broadcast packing (opens in a new tab)

  4. 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 …

    houston Repository record for Sampling of Random Graphs with Prescribed Degree Sequence (opens in a new tab)

  5. 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.

    uiuc Repository record for On Induced Subgraphs, Degree Sequences, and Graph Structure (opens in a new tab)

  6. 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: …

    greece Repository record for Algorithms and complexity of graph modification problems (opens in a new tab)

  7. 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 …

    regina Repository record for Lower Bounds and Algorithms for Searching Networks (opens in a new tab) Download PDF for Lower Bounds and Algorithms for Searching Networks (opens in a new tab)

  8. 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>. …

    waterloo Repository record for A New Optimality Measure for Distance Dominating Sets (opens in a new tab)

  9. 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 …

    uvic Repository record for On End Vertices of Search Algorithms (opens in a new tab)

  10. 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.

    vt Repository record for Essays on Network formation games (opens in a new tab)

  11. 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 …

    waterloo Repository record for Combinatorial Generalizations of Sieve Methods and Characterizing Hamiltonicity via Induced Subgraphs (opens in a new tab)

  12. 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 …

    brazil-uerj Repository record for On (in)tractability of connection and cut problems (opens in a new tab)

  13. 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 …

    waterloo Repository record for On the Complexity of Reconfiguration of Clique, Cluster Vertex Deletion, and Dominating Set (opens in a new tab)

  14. 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 …

    greece Repository record for Edge modification on perfect and reducible graphs with application to watermarking (opens in a new tab)

  15. 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 …

    fu-berlin Repository record for Modularity in Biological Networks (opens in a new tab)

  16. 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.

    brazil-ufrgs Repository record for Energia laplaciana sem sinal de grafos (opens in a new tab)

  17. 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 …

    clemson Repository record for Large-Scale Optimization Models with Applications in Biological and Emergency Response Networks (opens in a new tab)

  18. ΠΑΡΑΛΛΗΛΟΙ ΑΛΓΟΡΙΘΜΟΙ ΓΙΑ ΠΡΟΒΛΗΜΑΤΑ ΤΕΛΕΙΩΝ ΓΡΑΦΗΜΑΤΩΝ

    … 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 . …

    greece Repository record for ΠΑΡΑΛΛΗΛΟΙ ΑΛΓΟΡΙΘΜΟΙ ΓΙΑ ΠΡΟΒΛΗΜΑΤΑ ΤΕΛΕΙΩΝ ΓΡΑΦΗΜΑΤΩΝ (opens in a new tab)