• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Obstructions for local tournament orientation completions

Hsu, Kevin 23 August 2020 (has links)
The orientation completion 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 graphs and the representation extension problem for proper interval graphs. A local tournament is an oriented graph in which the in-neighbourhood as well as the out-neighbourhood of each vertex induces a tournament. Local tournaments are a well-studied class of oriented graphs that generalize tournaments and their underlying graphs are intimately related to proper circular-arc graphs. Proper interval graphs are precisely those which can be oriented as acyclic local tournaments. The orientation completion problems for the class of local tournaments and the class of acyclic local tournaments have been shown to be polynomial-time solvable. In this thesis, we characterize the partially oriented graphs that can be completed to local tournaments by finding a complete list of obstructions. These are in a sense the minimal partially oriented graphs that cannot be completed to local tournaments. We also determine the minimal partially oriented graphs that cannot be completed to acyclic local tournaments. / Graduate

Page generated in 0.0786 seconds