Name
Abstract | ||
|---|---|---|
We describe a consensus-type algorithm for determining all the maximal complete bipartite (not necessarily induced) subgraphs of a graph. We show that by imposing a particular order in which the consensus type operations should be executed, this algorithm becomes totally polynomial. By imposing a further restriction on the way the algorithm has to be executed, we derive an improved variant of it, the complexity of which is bounded by a polynomial that is cubic in the input size, and only linear in the output size, and show its high efficiency on numerous computational experiments on randomly generated graphs with up to 1000 vertices and 6000 edges. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/j.dam.2003.09.004 | Consensus Algorithms for the Generation of all Maximal Bicliques |
Keywords | Field | DocType |
input size,complete bipartite,incrementally polynomial,Algorithmic graph theory,high efficiency,new algorithm,consensus algorithm,maximal bicliques,computational experiment,output size,consensus method,efficient variant,Consensus-type algorithm,Maximal complete bipartite subgraph,induced subgraphs,Incremental polynomial enumeration,Biclique | Complete bipartite graph,Discrete mathematics,Consensus algorithm,Graph,Combinatorics,Bipartite graph,Algorithmic graph theory,Mathematics | Journal |
Volume | Issue | ISSN |
145 | 1 | Discrete Applied Mathematics |
Citations | PageRank | References |
75 | 3.86 | 18 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gabriela Alexe | 1 | 197 | 12.75 |
| sorin alexe | 2 | 169 | 10.56 |
| Yves Crama | 3 | 547 | 63.94 |
| Stephan Foldes | 4 | 175 | 19.36 |
| Peter L. Hammer | 5 | 1996 | 288.93 |
| Bruno Simeone | 6 | 496 | 54.36 |