2006 · 12 citations · 2 references
ComputingComputer ScienceMathematicsAlgorithmsDiscrete MathematicsApproximation AlgorithmsConstraint SatisfactionGraph AlgorithmsGraph TheoryComputational Complexity Of Graph AlgorithmsIntegrity Check Algorithms
Network reliability is an important issue in the area of distributed computing. Most of the early work in this area takes a probabilistic approach to the problem. However, sometimes it is important to incorporate subjective reliability estimates into the measure. To serve this goal, we propose the use of the weighted integrity, a measure of graph vulnerability. The weighted integrity problem is known to be NP-complete for most of the common network topologies including tree, mesh, hypercube etc. It is known to be NP-complete even for most perfect graphs, including comparability graphs and chordal graphs. However, the computational complexity of the problem is not known for one class of perfect graphs, namely, co-comparability graphs. In this paper we give a polynomial time algorithm to compute the weighted integrity of interval graphs, a subclass of co-comparability graphs.
2
Kunwarjit S. Bagga, Lowell W. Beineke, Wayne Goddard et al. · Discrete Applied Mathematics · 1992 · 95 citations
On the honesty of graph complements
Kunwarjit S. Bagga, Lowell W. Beineke, Marc J. Lipman et al. · Discrete Mathematics · 1993 · 12 citations