Algorithmic aspects of bipartite graphs
We generalize previous work done by Donald J. Rose and Robert E. Tarjan [2], who developed efficient algorithms for use on directed graphs. This paper considers an edge elimination process on bipartite graphs, presenting several theorems which lead to an algorithm for computing the minimal fill-in o...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
1995-01-01
|
| Series: | International Journal of Mathematics and Mathematical Sciences |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1155/S0161171295000378 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832568247463968768 |
|---|---|
| author | Mihály Bakonyi Erik M. Varness |
| author_facet | Mihály Bakonyi Erik M. Varness |
| author_sort | Mihály Bakonyi |
| collection | DOAJ |
| description | We generalize previous work done by Donald J. Rose and Robert E. Tarjan [2],
who developed efficient algorithms for use on directed graphs. This paper considers an edge
elimination process on bipartite graphs, presenting several theorems which lead to an algorithm
for computing the minimal fill-in of a given ordered graph. |
| format | Article |
| id | doaj-art-d0f1a5d7de2f4c9da697204092bd37ba |
| institution | Kabale University |
| issn | 0161-1712 1687-0425 |
| language | English |
| publishDate | 1995-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Mathematics and Mathematical Sciences |
| spelling | doaj-art-d0f1a5d7de2f4c9da697204092bd37ba2025-02-03T00:59:28ZengWileyInternational Journal of Mathematics and Mathematical Sciences0161-17121687-04251995-01-0118229930410.1155/S0161171295000378Algorithmic aspects of bipartite graphsMihály Bakonyi0Erik M. Varness1Department of Mathematics, Georgia State University, Atlanta, GA 30303, USADepartment of Mathematics, Valparaiso University, Valparaiso, Indiana 46383, USAWe generalize previous work done by Donald J. Rose and Robert E. Tarjan [2], who developed efficient algorithms for use on directed graphs. This paper considers an edge elimination process on bipartite graphs, presenting several theorems which lead to an algorithm for computing the minimal fill-in of a given ordered graph.http://dx.doi.org/10.1155/S0161171295000378Gaussian eliminationbipartite graphperfect edge elimination fill-in. |
| spellingShingle | Mihály Bakonyi Erik M. Varness Algorithmic aspects of bipartite graphs International Journal of Mathematics and Mathematical Sciences Gaussian elimination bipartite graph perfect edge elimination fill-in. |
| title | Algorithmic aspects of bipartite graphs |
| title_full | Algorithmic aspects of bipartite graphs |
| title_fullStr | Algorithmic aspects of bipartite graphs |
| title_full_unstemmed | Algorithmic aspects of bipartite graphs |
| title_short | Algorithmic aspects of bipartite graphs |
| title_sort | algorithmic aspects of bipartite graphs |
| topic | Gaussian elimination bipartite graph perfect edge elimination fill-in. |
| url | http://dx.doi.org/10.1155/S0161171295000378 |
| work_keys_str_mv | AT mihalybakonyi algorithmicaspectsofbipartitegraphs AT erikmvarness algorithmicaspectsofbipartitegraphs |