CSE 591 Project Topics

A

Projects that explore an open problem in combinatorial reliability theory, its application to communications networks, or the underlying combinatorics in matroid theory, network flows, enumeration, or the like. No computer implementation is expected (or desired) for this type of project. A critical literature review that suggests directions for interesting research is quite appropriate here; a rehash of well-surveyed topics is not.

B

Projects that explore the effective use of combinatorial results in reliability theory. This would include improvements to existing methods, effective ways to implement existing methods, or comparison of existing methods.

C

Projects that implement a nontrivial reliability algorithm. The emphasis here is on understanding the algorithm, and implementing it correctly and efficiently. Depending on the method chosen, some comparison with existing methods already implemented may be appropriate.

D

Projects that explore applications of the results of combinatorial reliability theory in more complicated settings for communications networks (such as expected flow, expected distance), or to novel application areas (database systems, transportation networks, fire spread)

1. the project is self-contained and not easily extensible;
2. the topic is limited, but too large to explore completely in the project;
3. the topic would extend nicely to an Master's thesis topic;
4. the topic would extend nicely to a Ph.D. topic;
5. one could effectively spend an academic lifetime exploring the topic.

A4

Is there an efficient method for calculating the number of spanning, connected, unicyclic subgraphs of a graph? (A3) Is there an efficient method of getting tight bounds on this number?

A4

Are the coefficients of the reliability polynomial strongly log-concave for the polynomial in standard form? in F-form? in H-form? (A3) Find classes of graphs for which such strong log-concavity results do hold.

A3

What is the complexity of finding the edge-packing by cutsets that leads to the best two-terminal upper bound?

A4

Explore Chari's theory of F-complexes for undirected k-terminal reliability problems, with a view to extending the theory to reliability problems on directed networks.

A5

Develop tight upper bounds on F-vectors and H-vectors of matroids, or of graphic matroids (graphs), or of cographic matroids (duals of graphs). (A2) Can one find a single general inequality that tightens Stanley's inequalities for shellable complexes? (some computation may help here)

A5

This is a good problem for someone with a strong algebraic inclination. Develop an explicit combinatorial correspondence between the spanning trees of a graph and the multisets in the multicomplex of monomials whose existence follows from Stanley's theorem. (A4) is this multicomplex pure?

B2

Devise and implement an all-terminal analogue of Fishman's Monte Carlo algorithm based on edge-packing bounds.

D1

Explore the application of reliability algorithms and bounds to the computation of probabilistic transitive closure, and examine potential applications in database and hypertext retrieval systems.

D2

Explore the application of reliability algorithms to fire spread, or to the spread of noxious substances.

D4

Explore the application of reliability algorithms in location problems: for example, in a distributed system, where can we best locate servers to enhance reliability?

C3

Combine Fishman's Monte Carlo algorithm using edge-packing bounds with the series-parallel bounds to obtain a Monte Carlo algorithm for two-terminal reliability that is based on the series-parallel bounds.

C2

Implement the Karp-Luby algorithm for all-terminal reliability, and examine its performance compared to all-terminal bounds.

D2

Explore the application of series-parallel bounds to the computation of expected flow and expected distance in a network.

C2

Implement bounding methods for reliability that rely on the computation of ``most probable states'' of the network. How do these compare to alternative approaches?

C1

Implement an exact Boolean algebra method for calculating network reliability.

C1

Implement Buzacott's algorithm for network reliability.

B2

Implement the Feo-Provan algorithm for Delta-Y reduction of a planar graph, and examine its use in computing bounds for two-terminal reliability of planar graphs.

D3

Explore the literature on inference and causation in probabilistic networks (which are used to represent your ``belief'' in certain propositions based upon your belief in others). How does probabilistic inference relate to network reliability?

A3

For every choice of number of edges (m) and number of vertices (n), prove that there is a single connected graph L_{n,m} with the property that, for every value 0 \leq p \leq 1 of the operation probability of each edge, every n-vertex m-edge connected graph has at least as high a probability of connectedness as L_{n,m}. This appears not to be difficult, but has been remarkably obstinate.