Connectivity calculus

• Given a finite hypergraph H = (V, E) and, for each e E E, a collection of nonempty subsets pi(e) of e, Mobius inversion is used to establish a recursive formula for the number of connected components of the hypergraph H = (V, boolean OR(eis an element ofE)pi(e)). As shown elsewhere, this formula is an essential ingredient in the context of a certain divide-and-conquer strategy that allows us to define a dynamical programming scheme solving Steiner's problem for graphs in linear time (however, with a constant depending hyperexponentially on their tree width).

Ämnesord

NATURVETENSKAP  -- Matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics (hsv//eng)

Nyckelord

MATHEMATICS

MATEMATIK

Publikations- och innehållstyp

ref (ämneskategori)

art (ämneskategori)