• About
    • Login
    View Item 
    •   Institutional Repository Home
    • Electronic Theses and Dissertations
    • Electronic Theses and Dissertations
    • View Item
    •   Institutional Repository Home
    • Electronic Theses and Dissertations
    • Electronic Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Browse

    All of Institutional RepositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    A generalization of chordal graphs

    Bonnin Cadogan, Jose M
    : https://etd.library.vanderbilt.edu/etd-07222011-120507
    http://hdl.handle.net/1803/13439
    : 2011-08-01

    Abstract

    This thesis introduces graph class C, a recognition algorithm for graphs in the class, and shows that some problems are NP-complete on the class. Class C is a generalization of chordal graphs. Informally, a graph is in class C if successively removing the neighborhoods of its simplicial vertices produces a null graph. More precisely, a graph G is in class C if G is the null graph or G contains a simplicial vertex v such that G - N[v] is in C. A greedy algorithm can recognize whether a graph is in class C in O(nm) time. The maximum independent set problem and the clique cover problem on class C can be solved in linear time using greeedy algorithms. However, the maximum clique problem and the coloring problem are NP-complete on the class. This work also examines class K, the class of graphs in class C whose complements are also in class C, and shows that the maximum weighted independent set problem is NP-complete on the class. Class K generalizes split graphs, the class of graphs that are chordal and co-chordal. The four problems mentioned in relation to class C can be solved in linear time on class K using greedy algorithms. The same is known to be true for split graphs. However, while the maximum weighted independent set problem can be solved in polynomial time on split graphs, this problem is NP-complete on class K.
    Show full item record

    Files in this item

    Icon
    Name:
    Bonnin.pdf
    Size:
    233.9Kb
    Format:
    PDF
    View/Open

    This item appears in the following collection(s):

    • Electronic Theses and Dissertations

    Connect with Vanderbilt Libraries

    Your Vanderbilt

    • Alumni
    • Current Students
    • Faculty & Staff
    • International Students
    • Media
    • Parents & Family
    • Prospective Students
    • Researchers
    • Sports Fans
    • Visitors & Neighbors

    Support the Jean and Alexander Heard Libraries

    Support the Library...Give Now

    Gifts to the Libraries support the learning and research needs of the entire Vanderbilt community. Learn more about giving to the Libraries.

    Become a Friend of the Libraries

    Quick Links

    • Hours
    • About
    • Employment
    • Staff Directory
    • Accessibility Services
    • Contact
    • Vanderbilt Home
    • Privacy Policy