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 20 of 34 for “"Interval Graphs"”.

  1. Random Interval Graphs

    … by Dr. David Penman, we examine random interval graphs. Recall that such a graph is defined by letting $X_{1},\ldots X_{n},Y_{1},\ldots Y_{n}$ be $2n$ independent random variables, with uniform distribution on $[0,1]$. We then say that the $i$th of the $n$ vertices is the interval …

    essex Download PDF for Random Interval Graphs (opens in a new tab)

  2. Dynamic algorithms for chordal and interval graphs

    … additional properties when the input graph is interval. We then introduce the train tree representation of interval graphs and use it to decide whether there is a certain linear ordering of the graph's maximal cliques. This yields a fully dynamic algorithm to recognize interval graphs in O(n …

    uvic Repository record for Dynamic algorithms for chordal and interval graphs (opens in a new tab)

  3. A Faster Algorithm for Recognizing Edge-Weighted Interval Graphs

    Interval graphs—the intersection graphs of one-dimensional intervals—are considered one of the most useful mathematical structures to model real life applications. Interval graphs have been widely studied since they first appeared in the literature in 1957. In 1976, Booth and Lueker introduced a …

    waterloo Repository record for A Faster Algorithm for Recognizing Edge-Weighted Interval Graphs (opens in a new tab)

  4. Dynamic representation of consecutive-ones matrices and interval graphs

    … we obtain an O(n) algorithm for updating an interval model of an interval graph when an edge or vertex is added or deleted. This matches the bounds obtained by a previous dynamic interval-graph recognition algorithm due to Crespelle. We improve on Crespelle's result by producing an …

    colostate Repository record for Dynamic representation of consecutive-ones matrices and interval graphs (opens in a new tab)

  5. Succinct and Compact Data Structures for Intersection Graphs

    … structures for several classes of intersection graphs, including interval graphs, path graphs and chordal graphs. Our goal is to support navigational operations such as adjacent and neighbourhood and distance operations such as distance efficiently while occupying optimal space, or a constant …

    waterloo Repository record for Succinct and Compact Data Structures for Intersection Graphs (opens in a new tab)

  6. Chronological rectangle digraphs

    Interval graphs admit elegant ordering and structural characterizations. A natural digraph analogue of interval graphs, called chronological interval digraphs, has recently been identified and studied. We introduce the class of chronological rectangle digraphs, and show that they are a higher …

    uvic Repository record for Chronological rectangle digraphs (opens in a new tab)

  7. Simultaneous Graph Representation Problems

    Many graphs arising in practice can be represented in a concise and intuitive way that conveys their structure. For example: A planar graph can be represented in the plane with points for vertices and non-crossing curves for edges. An interval graph can be represented on the real line with …

    waterloo Repository record for Simultaneous Graph Representation Problems (opens in a new tab)

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

  9. Interval Digraphs

    We say that a simple, undirected graph interval graph if there exists a function mapping the vertices of the graph to intervals such that each pair of vertices is adjacent if and only if the corresponding intervals have a non-empty intersection. Undirected interval graphs were originally of …

    jhu Repository record for Interval Digraphs (opens in a new tab)

  10. Obstructions for local tournament orientation completions

    … problem for a hereditary class C of oriented graphs asks whether a given partially oriented graph can be completed to a graph belonging to C. This problem was introduced recently and is a generalization of several existing problems, including the recognition problem for certain classes of …

    uvic Repository record for Obstructions for local tournament orientation completions (opens in a new tab)

  11. Indifference Graphs and the Single Row Routing Problem

    This thesis investigates the subclass of interval graphs known as indifference graphs. New optimal algorithms for recognition, center, diameter, maximum matching, Hamiltonian path and domination in indifference graphs are presented. The recognition algorithm produces a linear order with properties …

    odu Repository record for Indifference Graphs and the Single Row Routing Problem (opens in a new tab)

  12. Minimum Latency Aggregation Convergecast in Wireless Sensor Networks

    … been proven to be NP-Complete even for unit disk graphs. We present a new simpler proof of the NP-Completeness of the MLAS Problem for arbitrary networks and unit disk graphs. We give tight bounds for the latency of aggregation convergecast for grids, tori, and trees. For regular unit interval …

    concordia Download PDF for Minimum Latency Aggregation Convergecast in Wireless Sensor Networks (opens in a new tab)

  13. On (in)tractability of connection and cut problems

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

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

  14. A Linear Algebraic Method on the Chromatic Symmetric Function

    … of the chromatic symmetric functions of unit-interval graphs, this conjecture has served as a significant motivator of research in algebraic graph theory in recent years. We summarize a great deal of the existing work done in favor of this conjecture, giving an overview of the various …

    waterloo Repository record for A Linear Algebraic Method on the Chromatic Symmetric Function (opens in a new tab)

  15. Προσεγγιστικά σχήματα, κλίκες, χρώματα και πυκνότεροι υπογράφοι

    … for the densest k-subgraph problem on weighted graphs of maximal degree two, on weighted trees even if the solution is disconnected, and on interval graphs with intersection only between two consecutive cliques. Moreover, we present a polynomial time approximation scheme for the densest …

    greece Repository record for Προσεγγιστικά σχήματα, κλίκες, χρώματα και πυκνότεροι υπογράφοι (opens in a new tab)

  16. Connections between Hessenberg varieties, chromatic quasisymmetric functions, and q-series

    … that the chromatic symmetric functions for unit interval graphs expanded with positive coefficients in the basis of elementary symmetric functions. This conjecture has been proved directly for several families of graphs, and a recent full proof was proposed by Hikita in 2024. Geometrically, this …

    colostate Repository record for Connections between Hessenberg varieties, chromatic quasisymmetric functions, and q-series (opens in a new tab)

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

  18. Pattern sequencing models in cutting stock problems

    … associating the duration of each stack with an interval of time, it is possible to use the rich theory that exists in interval graphs in order to create a model based on the completion of a graph with edges. The structure of this type of graphs admits a linear ordering of the vertices that de …

    minho-thes Repository record for Pattern sequencing models in cutting stock problems (opens in a new tab)

  19. Generalizations of comparability graphs

    … if there is such an assignment. Comparability graphs are a class of graphs where clique, coloring, and many other optimization problems are solved by polynomial algorithms. It also has close connections with other classes of graphs, such as interval graphs, permutation graphs, and perfect …

    colostate Repository record for Generalizations of comparability graphs (opens in a new tab)

  20. Transversals of Geometric Objects and Anagram-Free Colouring

    … question in Wilson's thesis and shows that even graphs of pathwidth 2 do not have anagram-free colouring with a bounded number of colours. The third article is a study on the geodesic anagram-free chromatic number of chordal and interval graphs. \emph{Geodesic anagram-free chromatic number} is …

    ottawa-retro Repository record for Transversals of Geometric Objects and Anagram-Free Colouring (opens in a new tab)

Page 1 of 2