DC Field | Value | Language |
---|---|---|
dc.contributor.author | Glock, Stefan | ko |
dc.contributor.author | Joos, Felix | ko |
dc.contributor.author | Kim, Jaehoon | ko |
dc.contributor.author | Kühn, Marcus | ko |
dc.contributor.author | Lichev, Lyuben | ko |
dc.date.accessioned | 2023-07-12T12:00:49Z | - |
dc.date.available | 2023-07-12T12:00:49Z | - |
dc.date.created | 2023-07-08 | - |
dc.date.created | 2023-07-08 | - |
dc.date.issued | 2023-01-24 | - |
dc.identifier.citation | ACM-SIAM Symposium on Discrete Algorithms (SODA23), pp.2991 - 3005 | - |
dc.identifier.uri | http://hdl.handle.net/10203/310449 | - |
dc.description.abstract | A celebrated theorem of Pippenger, and Frankl and Rödl states that every almost-regular, uniform hypergraph H with small maximum codegree has an almost-perfect matching. We extend this result by obtaining a conflict-free matching, where conflicts are encoded via a collection C of subsets C ⊆ E (H). We say that a matching M ⊆ E (H) is conflict-free if M does not contain an element of C as a subset. Under natural assumptions on C, we prove that H has a conflict-free, almost-perfect matching. This has many applications, one of which yields new asymptotic results for so-called “high-girth” Steiner systems. Our main tool is a polynomial time random greedy algorithm which we call the “conflict-free matching process”. | - |
dc.language | English | - |
dc.publisher | Society for Industrial and Applied Mathematics | - |
dc.title | Conflict-free hypergraph matchings | - |
dc.type | Conference | - |
dc.type.rims | CONF | - |
dc.citation.beginningpage | 2991 | - |
dc.citation.endingpage | 3005 | - |
dc.citation.publicationname | ACM-SIAM Symposium on Discrete Algorithms (SODA23) | - |
dc.identifier.conferencecountry | IT | - |
dc.identifier.conferencelocation | Florence | - |
dc.identifier.doi | 10.1137/1.9781611977554.ch115 | - |
dc.contributor.localauthor | Kim, Jaehoon | - |
dc.contributor.nonIdAuthor | Glock, Stefan | - |
dc.contributor.nonIdAuthor | Joos, Felix | - |
dc.contributor.nonIdAuthor | Kühn, Marcus | - |
dc.contributor.nonIdAuthor | Lichev, Lyuben | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.