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, 395-399 p.Article 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, 395-399 p.
National Category
Mathematics
Identifiers
URN: urn:nbn:se:miun:diva-13652ISI: 000181777900023Scopus ID: 2-s2.0-84867985841OAI: oai:DiVA.org:miun-13652DiVA: diva2:411889
Available from: 2011-04-19 Created: 2011-04-19 Last updated: 2015-03-19Bibliographically approved

Open Access in DiVA

No full text

Scopus

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

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