Browsing by Author "Proskurowski, Andrzej"

Now showing 1 - 3 of 3
  • Thumbnail Image
    ItemOpen Access
    Broadcasting in Trees with Multiple Originators
    (University of Oregon, 1980) Farley, Arthur M.; Proskurowski, Andrzej
    Broadcasting is the information dissemination process in a communication network whereby all sites of the network become informed of a given message by calls made over lines of the network. We present an algorithm which, given a tree network and a time, determines a smallest set of subtrees covering sites of the network such that broadcast can be completed within the given time in each subtree. Information developed by the algorithm is sufficient to determine a satisfactory originator and calling scheme within each subtree.
  • Thumbnail Image
    ItemOpen Access
    The Design of Template Immune Networks: Path Immunity
    (University of Oregon, 1989-03-24) Farley, Arthur M.; Proskurowski, Andrzej
    A network is specified by a topology definition and a protocol definition. A network's topology, represented as a graph, defines its interconnection structure, while the protocol defines its operational behavior. A template is a connected graph. A topology G is immune to a set of templates T if G remains connected under removal of any imbedding of a single element of T. A network is template immune to a set of templates T if its topology is immune to T and its protocol guarantees that all operative sites can communicate in the presence of possible failures. A network is isolated template immune to a set of templates T if it is immune to multiple imbeddings of elements of T, where each imbedded template does not involve vertices that are neighbors of another imbedded template. We discuss networks that are isolated template immune to simple path templates of length k.
  • Thumbnail Image
    ItemOpen Access
    Fast Parallel Algorithms for the Subgraph Homeomorphism & the Subgraph Isomorphism Problems for Classes of Planar Graphs
    (University of Oregon, 1988-04-06) Lingas, Andrzej; Proskurowski, Andrzej
    We consider the problems of subgraph homeomorphism with fixed pattern graph, recognition, and subgraph isomorphism for some classes of planar graphs. Following the results of Robertson and Seymour on forbidden minor characterization, we show that the problems of fixed subgraph homeomorphism and recognition for any family of planar graphs closed under minor taking are in NC (i.e., they can be solved by an algorithm running in poly-log time using polynomial number of processors). We also show that the related subgraph isomorphism problem for biconnected outerplanar ·graphs is in NC. This is the first example of a restriction of subgraph isomorphism to a non-trivial graph family admitting an NC algorithm