miun.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Connectivity calculus
Mid Sweden University, Faculty of Science, Technology and Media, Department of Engineering, Physics and Mathematics.
Mid Sweden University, Faculty of Science, Technology and Media, Department of Engineering, Physics and Mathematics.
2003 (English)In: Applied Mathematics Letters, ISSN 0893-9659, E-ISSN 1873-5452, Vol. 16, no 3, p. 395-399Article in journal (Refereed) Published
Abstract [en]

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).

Place, publisher, year, edition, pages
2003. Vol. 16, no 3, p. 395-399
National Category
Mathematics
Identifiers
URN: urn:nbn:se:miun:diva-13652ISI: 000181777900023Scopus ID: 2-s2.0-84867985841OAI: oai:DiVA.org:miun-13652DiVA, id: diva2:411889
Available from: 2011-04-19 Created: 2011-04-19 Last updated: 2017-12-11Bibliographically approved

Open Access in DiVA

No full text in DiVA

Scopus

Authority records BETA

Huber, Katharina TMoulton, Vincent

Search in DiVA

By author/editor
Huber, Katharina TMoulton, Vincent
By organisation
Department of Engineering, Physics and Mathematics
In the same journal
Applied Mathematics Letters
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 32 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf