Carnegie Mellon University
Browse

Topics in Information Dissemination, Network Fortification and Extremal Structures

Download (989.56 kB)
thesis
posted on 2022-10-24, 21:42 authored by Da Qi ChenDa Qi Chen

This thesis considers several problems in Combinatorial Optimization and Extremal Graph theory. In Combinatorial Optimization, the goal is to find efficient algorithms or near-optimal approximations of natural questions in networks. In Extremal Graph Theory, the objective is often determining the extremal graphs that maximizes/minimizes some specific subgraph while obeying certain local structural constraints.

In Chapter 2, we propose and study a new model of disseminating information from a root called the Vector Clock Model. We provide several near-optimal approximation schedules that best distribute newly-formed information to all nodes in the graph.

Chapter 3 contains interdiction problems where an attacker with a limited budget wish to destroy the edge-connectivity of a graph as much as possible. We introduce a generalization called Vertex Downgrading and provides bicriteria approximations for this provably-hard-to-approximate problem.

The goal of the problems in Chapter 4 is to increase the weight of individual edges in a graph in order to maximize the increase of the weight of a Minimum Spanning Tree. We provide a constant approximation to a unit discrete model and provides a correction to a solution provided by Frederickson and Solis-Oba in [45] for the continuous model.

In Chapter 5 and 6, we study generalized Tur´an problems where the obajective is to maximize the number of cliques of a certain size given the graph has a fixed number of vertices (or edges) and does not contain a specific subgraph (such as a star of a fixed size or paths/cycles of a certain length). We provide the complete characterization of the extremal graphs to these questions.

Lastly, in Chapter 7, we investigate a bipartite saturation problem that was first studied over fifty years ago. We confirm a conjecture by Moshkovitz and Shapira for a special case, with the classification of the extremal graphs. We also improve the estimates of Gan, Kor´andi, and Sudakov for the general problem..

Funding

DESIGNING PROVABLY GOOD HEURISTICS FOR RAPID INFORMATION DISSEMINATION PROBLEMS

United States Department of the Air Force

Find out more...

History

Date

2022-08-16

Degree Type

  • Dissertation

Department

  • Mathematical Sciences

Degree Name

  • Doctor of Philosophy (PhD)

Advisor(s)

R. Ravi

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC