Advanced search options

You searched for `subject:(clique cutset)`

. One record found.

▼ Search Limiters

Wilfrid Laurier University

1. Gorbonos, Elizabeth. Separability and Vertex Ordering of Graphs.

Degree: 2019, Wilfrid Laurier University

URL: https://scholars.wlu.ca/etd/2148

Many graph optimization problems, such as finding an optimal coloring, or a largest clique, can be solved by a divide-and-conquer approach. One such well-known technique is decomposition by clique separators where a graph is decomposed into special induced subgraphs along their clique separators. While the most common practice of this method employs minimal clique separators, in this work we study other variations as well. We strive to characterize their structure and in particular the bound on the number of atoms. In fact, we strengthen the known bounds for the general clique cutset decomposition and the minimal clique separator decomposition. Graph ordering is the arrangement of a graphâ€™s vertices according to a certain logic and is a useful tool in optimization problems. Special types of vertices are often recognized in graph classes, for instance it is well-known every chordal graph contains a simplicial vertex. Vertex-ordering, based on such properties, have originated many linear time algorithms. We propose to define a new family named SE-Class such that every graph belonging to this family inherently contains a simplicial extreme, that is a vertex which is either simplicial or has exactly two neighbors which are non-adjacent. Our family lends itself to an ordering based on simplicial extreme vertices (named SEO) which we demonstrate to be advantageous for the coloring and maximum clique problems. In addition, we examine the relation of SE-Class to the family of (Even-Hole, Kite)-free graphs and show a linear time generation of SEO for (Even-Hole, Diamond, Claw)-free graphs. We showcase the applications of those two core tools, namely clique-based decomposition and vertex ordering, on the (Even-Hole, Kite)-free family.

Subjects/Keywords: graph theory; decomposition; clique cutset; simplicial extreme; even-hole; kite; Theory and Algorithms

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Gorbonos, E. (2019). Separability and Vertex Ordering of Graphs. (Thesis). Wilfrid Laurier University. Retrieved from https://scholars.wlu.ca/etd/2148

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} Edition):

Gorbonos, Elizabeth. “Separability and Vertex Ordering of Graphs.” 2019. Thesis, Wilfrid Laurier University. Accessed November 24, 2020. https://scholars.wlu.ca/etd/2148.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Gorbonos, Elizabeth. “Separability and Vertex Ordering of Graphs.” 2019. Web. 24 Nov 2020.

Vancouver:

Gorbonos E. Separability and Vertex Ordering of Graphs. [Internet] [Thesis]. Wilfrid Laurier University; 2019. [cited 2020 Nov 24]. Available from: https://scholars.wlu.ca/etd/2148.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Gorbonos E. Separability and Vertex Ordering of Graphs. [Thesis]. Wilfrid Laurier University; 2019. Available from: https://scholars.wlu.ca/etd/2148

Not specified: Masters Thesis or Doctoral Dissertation