Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for subject:(clique cutset). One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


Wilfrid Laurier University

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

Degree: 2019, Wilfrid Laurier University

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 DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th 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 (16th 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 (7th 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

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

.