Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 18 of 18 for “"series-parallel graphs"”.

  1. Alliances In Graphs: Parameterized Algorithms And On Partitioning Series-parallel Graphs

    … and other entities. The notion of alliances in graphs was first introduced by Kristiansen, Hedetniemi, and Hedetniemi in . A defensive alliance in a graph G = (V, E) is a non empty set S ⊆ V where, for all x ∈ S, |N[x] ∩ S| ≥ |N[x] − S|. Consequently, every vertex that is a member of a defensive …

    ucf Repository record for Alliances In Graphs: Parameterized Algorithms And On Partitioning Series-parallel Graphs (opens in a new tab)

  2. D-width, metric embedding, and their connections

    … Shortest path metrics for trees and outerplanar graphs are isometrically embeddable into [cursive l]₁ [41]. Series-parallel graphs [28] and k-outerplanar graphs [19] (for constant k) are embeddable into[cursive l]₁ with constant distortion planar graphs and bounded tree-width graphs are …

    ubc Repository record for D-width, metric embedding, and their connections (opens in a new tab) Download PDF for D-width, metric embedding, and their connections (opens in a new tab)

  3. Construction of Reliable Series-Parallel Networks: A Combinatorial Approach

    … we can efficiently count connected spanning subgraphs classified by number of links. This thesis studies maximal series-parallel graphs (equivalent to a class of graphs known as 2-trees) and closely related graphs. We coin the term generalized fan to describe those maximal series-parallel …

    sask Repository record for Construction of Reliable Series-Parallel Networks: A Combinatorial Approach (opens in a new tab)

  4. Tolls For Atomic Congestion Games

    … the former case, we show that for the class of series-parallel graphs the nonatomic tolls suffice, and investigate examples for which nonatomic tolls fail. In the latter case, we show that the nonatomic tolls can also be used to impose flows in atomic laminar matroid games.

    waterloo Repository record for Tolls For Atomic Congestion Games (opens in a new tab)

  5. New algorithms for pathwidth computation

    … become polynomially solvable when restricted in graphs with bounded pathwidth (or treewidth). Practically, pathwidth and treewidth have significant applications in many different fields such as searching games, VLSI design, matrix computation, etc. Computing pathwidth is an NP-complete problem …

    rice Repository record for New algorithms for pathwidth computation (opens in a new tab)

  6. A Study of Four Network Problems in Transportation, Telecommunications, and Supply Chain Management

    … uncapacitated network design problems on series-parallel graphs, which have potential application in supply chain management. In the fifth chapter we study the arc routing problem that arises in the small package delivery industry. The last chapter summarizes the dissertation. The results …

    maryland Repository record for A Study of Four Network Problems in Transportation, Telecommunications, and Supply Chain Management (opens in a new tab)

  7. Negative Correlation Properties for Matroids

    … are B-Rayleigh. The I-Rayleigh difference for graphs on at most seven vertices is a sum of monomials times squares of polynomials and this same special form holds for all series parallel graphs.

    waterloo Repository record for Negative Correlation Properties for Matroids (opens in a new tab)

  8. Algorithms and Complexity for Alliances and Weighted Alliances of Various Types

    … complexity of decision problems for alliances in graphs. This thesis presents the first algorithmic study of alliances in graphs. We present linear algorithms for finding various alliance numbers in trees and series parallel graphs. These linear algorithms are designed using a new methodology …

    clemson Repository record for Algorithms and Complexity for Alliances and Weighted Alliances of Various Types (opens in a new tab)

  9. Linear-Time Algorithms for Edge-Based Problems

    … the variant can be applied to three classes of graphs: weighted trees, unicyclic graphs and generalized series-parallel graphs. For each of these classes, we detail what adaptations are required (if any) and design an algorithm, including showing a run on an example graph. The fourth chapter is …

    clemson Repository record for Linear-Time Algorithms for Edge-Based Problems (opens in a new tab)

  10. On k-level matroids: geometry and combinatorics

    … Theta-1 matroids which generalize the well-known series-parallel graphs. Moreover, we characterize the class of Theta-1 matroids in terms of the degree of generation of the vanishing ideal and in terms of the psd rank for the associated matroid base polytope. We analyze in full detail Theta-1 …

    fu-berlin Repository record for On k-level matroids: geometry and combinatorics (opens in a new tab)

  11. Generalized Colorings of Graphs

    … types of such generalizations in this thesis. Series-parallel graphs are multigraphs that have no K4-minor. We provide bounds on their fractional and circular chromatic numbers and the defective version of these pa-rameters. In particular we show that the fractional chromatic number of any …

    clemson Repository record for Generalized Colorings of Graphs (opens in a new tab)

  12. Weighted Modulo Orientations of Graphs

    … on the subject of nowhere-zero flow problems on graphs. Tutte's 5-Flow Conjecture (1954) states that every bridgeless graph admits a nowhere-zero 5-flow, and Tutte's 3-Flow Conjecture (1972) states that every 4-edge-connected graph admits a nowhere-zero 3-flow. Extending Tutte's flows …

    wvu Repository record for Weighted Modulo Orientations of Graphs (opens in a new tab)

  13. Characterizations of Some Classes of Graphs That Are Nearly Series-Parallel

    A series-parallel graph can be built from a single-edge graph by a sequence of series and parallel extensions. The class of such graphs coincides with the class of graphs that do not have the complete graph K4 as a minor. This dissertation considers a class M1 of graphs that are close to being …

    lsu-thes Repository record for Characterizations of Some Classes of Graphs That Are Nearly Series-Parallel (opens in a new tab)

  14. Domination : Offline, Online, Any Time

    … the domination number of a well-known family of graphs known as the Knödel graphs. Prior to this thesis, research on the dominating set problem in an online setting was sparse. We consider an online setting where a vertex is revealed to an algorithm and the choice to add this vertex or not is a …

    concordia Download PDF for Domination : Offline, Online, Any Time (opens in a new tab)

  15. Network synthesis problem : cost allocation and algorithms

    … embedded in (i.e., restricted to) some special graphs. Namely, when the requirement structure is sparse (because there are only a few demand nodes and the rest are just intermediate nodes) and the positive requirements are equal, we will employ a transformation procedure to simplify the …

    ubc Repository record for Network synthesis problem : cost allocation and algorithms (opens in a new tab) Download PDF for Network synthesis problem : cost allocation and algorithms (opens in a new tab)

  16. On some problems on k-trees and partial k-trees

    … k-complete subgraph. Partial k-trees are graphs embeddable in a k-tree with the same vertex set. They are natural generalizations of forests and series-parallel graphs which are the first two members of the hierarchy of partial k-trees. The many applications of k-trees and partial k-trees …

    ubc Repository record for On some problems on k-trees and partial k-trees (opens in a new tab) Download PDF for On some problems on k-trees and partial k-trees (opens in a new tab)

  17. ΑΝΑΘΕΣΗ ΕΡΓΑΣΙΩΝ ΣΕ ΚΑΤΑΝΕΜΗΜΕΝΑ ΥΠΟΛΟΓΙΣΤΙΚΑ ΣΥΣΤΗΜΑΤΑ: ΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΠΟΛΥΠΛΟΚΟΤΗΤΑ

    … COMMUNICATION PATTERN BETWEEN THE TASKS FORMS A SERIES-PARALLEL GRAPH. THE SECOND, AN EXHAUSTIVE SEARCH ALGORITHM, RELIES ON AN EFFICIENT LOWER BOUND THAT WE GENERATE BY DISREGARDING A NUMBER OF COMMUNICATION LINKS REDUCING THUS THE ORIGINAL COMMUNICATION STRUCTURE TO A TREE FOR WHICH THE …

    greece Repository record for ΑΝΑΘΕΣΗ ΕΡΓΑΣΙΩΝ ΣΕ ΚΑΤΑΝΕΜΗΜΕΝΑ ΥΠΟΛΟΓΙΣΤΙΚΑ ΣΥΣΤΗΜΑΤΑ: ΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΠΟΛΥΠΛΟΚΟΤΗΤΑ (opens in a new tab)