umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
The b-Matching Problem in Hypergraphs: Hardness and Approximability
Computer Science Institute, Christian-Albrechts-University of Kiel, Germany.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
2012 (Engelska)Ingår i: COCOA 2012: Combinatorial Optimization and Applications / [ed] Guohui Lin, Berlin-Heidelberg: Springer Berlin-Heidelberg , 2012, s. 200-211Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

In this paper we analyze the maximum cardinality b-matching problem in l-uniform hypergraphs with respect to the complexity class Max-Snp, where b-matching is defined as follows: for given b ∈ ℕ and a hypergraph H=(V,E)" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">H=(V,E)H=(V,E) a subset Mb&#x2286;E" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">Mb⊆EMb⊆E with maximum cardinality is sought so that no vertex is contained in more than b hyperedges of M b . We show that if the maximum degree of the vertices is bounded by a constant B ∈ ℕ , this problem has no approximation scheme, unless P=NP" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">P=NPP=NP. This result generalizes a result of Kann from b = 1 to the case that b ∈ ℕ with 0&lt;b&#x2264;B3" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">0<b≤B30<b≤B3. Furthermore, we extend a result of Srivastav and Stangier, who gave an approximation algorithm for the unweighted b-matching problem.

Ort, förlag, år, upplaga, sidor
Berlin-Heidelberg: Springer Berlin-Heidelberg , 2012. s. 200-211
Serie
Lecture Notes in Computer Science ; 7402
Nyckelord [en]
Hypergraphs, matching, L-reduction, Boolean satisfiability, randomized rounding, MAX-SNP-hardness
Nationell ämneskategori
Diskret matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-84483DOI: 10.1007/978-3-642-31770-5_18Libris ID: 13537064ISBN: 978-3-642-31770-5 (tryckt)OAI: oai:DiVA.org:umu-84483DiVA, id: diva2:684499
Konferens
6th International Conference, COCOA 2012, Banff, AB, Canada, August 5-9, 2012
Tillgänglig från: 2014-01-08 Skapad: 2014-01-08 Senast uppdaterad: 2019-04-24Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Jäger, Gerold

Sök vidare i DiVA

Av författaren/redaktören
Jäger, Gerold
Av organisationen
Institutionen för matematik och matematisk statistik
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 151 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf