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:

Sorted by: relevance · author · university · dateNew search

You searched for subject:(cone graph). Showing records 1 – 2 of 2 total matches.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


Colorado State University

1. Osnaga, Silvia Monica. Low rank representations of matrices using nuclear norm heuristics.

Degree: PhD, Mathematics, 2007, Colorado State University

The pursuit of low dimensional structure from high dimensional data leads in many instances to the finding the lowest rank matrix among a parameterized family of matrices. In its most general setting, this problem is NP-hard. Different heuristics have been introduced for approaching the problem. Among them is the nuclear norm heuristic for rank minimization. One aspect of this thesis is the application of the nuclear norm heuristic to the Euclidean distance matrix completion problem. As a special case, the approach is applied to the graph embedding problem. More generally, semi-definite programming, convex optimization, and the nuclear norm heuristic are applied to the graph embedding problem in order to extract invariants such as the chromatic number, Rn embeddability, and Borsuk-embeddability. In addition, we apply related techniques to decompose a matrix into components which simultaneously minimize a linear combination of the nuclear norm and the spectral norm. In the case when the Euclidean distance matrix is the distance matrix for a complete k-partite graph it is shown that the nuclear norm of the associated positive semidefinite matrix can be evaluated in terms of the second elementary symmetric polynomial evaluated at the partition. We prove that for k-partite graphs the maximum value of the nuclear norm of the associated positive semidefinite matrix is attained in the situation when we have equal number of vertices in each set of the partition. We use this result to determine a lower bound on the chromatic number of the graph. Finally, we describe a convex optimization approach to decomposition of a matrix into two components using the nuclear norm and spectral norm. Advisors/Committee Members: Kirby, Michael (advisor), Peterson, Chris (advisor), Bates, Dan (committee member), Wang, Haonan (committee member).

Subjects/Keywords: chromatic number; convex optimization; Euclidean distance matrix completion; graph realizability; positive semidefinite cone

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th Edition):

Osnaga, S. M. (2007). Low rank representations of matrices using nuclear norm heuristics. (Doctoral Dissertation). Colorado State University. Retrieved from http://hdl.handle.net/10217/83799

Chicago Manual of Style (16th Edition):

Osnaga, Silvia Monica. “Low rank representations of matrices using nuclear norm heuristics.” 2007. Doctoral Dissertation, Colorado State University. Accessed July 14, 2020. http://hdl.handle.net/10217/83799.

MLA Handbook (7th Edition):

Osnaga, Silvia Monica. “Low rank representations of matrices using nuclear norm heuristics.” 2007. Web. 14 Jul 2020.

Vancouver:

Osnaga SM. Low rank representations of matrices using nuclear norm heuristics. [Internet] [Doctoral dissertation]. Colorado State University; 2007. [cited 2020 Jul 14]. Available from: http://hdl.handle.net/10217/83799.

Council of Science Editors:

Osnaga SM. Low rank representations of matrices using nuclear norm heuristics. [Doctoral Dissertation]. Colorado State University; 2007. Available from: http://hdl.handle.net/10217/83799

2. Hunt, Alexis. Establishing a Connection Between Graph Structure, Logic, and Language Theory.

Degree: 2015, University of Waterloo

The field of graph structure theory was given life by the Graph Minors Project of Robertson and Seymour, which developed many tools for understanding the way graphs relate to each other and culminated in the proof of the Graph Minors Theorem. One area of ongoing research in the field is attempting to strengthen the Graph Minors Theorem to sets of graphs, and sets of sets of graphs, and so on. At the same time, there is growing interest in the applications of logic and formal languages to graph theory, and a significant amount of work in this field has recently been consolidated in the publication of a book by Courcelle and Engelfriet. We investigate the potential applications of logic and formal languages to the field of graph structure theory, suggesting a new area of research which may provide fruitful.

Subjects/Keywords: graph structure; logic; formal languages; language theory; monadic second-order logic; tree-decompositions; hyperedge replacement; HR algebra; graph theory; well-quasi-ordering; cone graph; cone ideal; tree-generator; obstruction-width

…chldrn(v) 4G fG G4 Children of v Cone of G Apex of 4G Cone graphs 8 45 45 46 G… …Powerset signature of F Graph obtained from G by forgetting the asource, if any Ideal with… …T ) Root vertex of T 8 viii Notation Description rena↔b (G) RG Graph… …The field of graph structre theory has grown considerably as a result of the Graph Minors… …called the Robertson-Seymour Theorem or simply the Graph Minor Theorem. The theorem states that… 

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th Edition):

Hunt, A. (2015). Establishing a Connection Between Graph Structure, Logic, and Language Theory. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/9648

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):

Hunt, Alexis. “Establishing a Connection Between Graph Structure, Logic, and Language Theory.” 2015. Thesis, University of Waterloo. Accessed July 14, 2020. http://hdl.handle.net/10012/9648.

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

MLA Handbook (7th Edition):

Hunt, Alexis. “Establishing a Connection Between Graph Structure, Logic, and Language Theory.” 2015. Web. 14 Jul 2020.

Vancouver:

Hunt A. Establishing a Connection Between Graph Structure, Logic, and Language Theory. [Internet] [Thesis]. University of Waterloo; 2015. [cited 2020 Jul 14]. Available from: http://hdl.handle.net/10012/9648.

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

Council of Science Editors:

Hunt A. Establishing a Connection Between Graph Structure, Logic, and Language Theory. [Thesis]. University of Waterloo; 2015. Available from: http://hdl.handle.net/10012/9648

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

.