This paper gives a new and faster algorithm to find a 1-factor in a bipartite D-regular graph. The time complexity of this algorithm is O(n D + n log n log D), where n is the number of nodes. This implies an O(n log n log D + m log D) algorithm to edge-color a bipartite graph with n nodes, m edges and maximum degree D.
Finding 1-factors in bipartite regular graphs, and edge-coloring bipartite graphs / Rizzi, Romeo. - ELETTRONICO. - (2002), pp. 1-6.
Finding 1-factors in bipartite regular graphs, and edge-coloring bipartite graphs
Rizzi, Romeo
2002-01-01
Abstract
This paper gives a new and faster algorithm to find a 1-factor in a bipartite D-regular graph. The time complexity of this algorithm is O(n D + n log n log D), where n is the number of nodes. This implies an O(n log n log D + m log D) algorithm to edge-color a bipartite graph with n nodes, m edges and maximum degree D.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
38.pdf
accesso aperto
Tipologia:
Versione editoriale (Publisher’s layout)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
212.47 kB
Formato
Adobe PDF
|
212.47 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione
