skip to main content

Search for: All records

Creators/Authors contains: "Dippel, Matthew"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. The classical Erdös-Gallai theorem kicked off the study ofgraph realizability by characterizing degree sequences. We extend this line of research by investigating realizability of directed acyclic graphs (DAGs)given both a local constraint via degree sequences and a global constraint via a sequence of reachability values (number of nodes reachable from a given node). We show that, without degree constraints, DAG reachability realization is solvable in linear time, whereas it is strongly NP-complete given upper bounds on in-degree or out-degree. After defining a suitable notion of bicriteria approximation based on consistency, we give two approximation algorithms achieving O(logn)-reachability consistency and O(logn)-degreemore »consistency; the first, randomized, uses LP (Linear Program) rounding, while the second, deterministic, employs ak-setpacking heuristic. We end with two conjectures that we hope motivate further study of realizability with reachability constraints.« less