Covering complete graphs using the dancing links algorithm

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F23%3A10254544" target="_blank" >RIV/61989100:27240/23:10254544 - isvavai.cz</a>
Výsledek na webu
<a href="https://www.scopus.com/record/display.uri?eid=2-s2.0-85175835533&origin=resultslist#funding-details" target="_blank" >https://www.scopus.com/record/display.uri?eid=2-s2.0-85175835533&origin=resultslist#funding-details</a>
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
Covering complete graphs using the dancing links algorithm
Popis výsledku v původním jazyce
The dancing links algorithm by Knuth can be used to find decompositions of a complete graph efficiently. In this paper, we generalize it to find covers of a complete graph by cliques as well. This problem arose as one step of a parallel implementation of the bounded element method when solving partial differential equations. The modification brought up an issue of counting certain covers of multiple edges multiple times. Having solved the problem by imposing a natural order, we show the computational results achieved by the modified algorithm.
Název v anglickém jazyce
Covering complete graphs using the dancing links algorithm
Popis výsledku anglicky
The dancing links algorithm by Knuth can be used to find decompositions of a complete graph efficiently. In this paper, we generalize it to find covers of a complete graph by cliques as well. This problem arose as one step of a parallel implementation of the bounded element method when solving partial differential equations. The modification brought up an issue of counting certain covers of multiple edges multiple times. Having solved the problem by imposing a natural order, we show the computational results achieved by the modified algorithm.

Rok uplatnění
2023
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Podobné výsledky(10)