Name
Title | ||
|---|---|---|
Generation of maximum independent sets of a bipartite graph and maximum cliques of a circular-arc graph |
Abstract | ||
|---|---|---|
We present an efficient algorithm for generating all maximum independent sets of a bipartite graph. Its time complexity is O(n2.5 + (output size)), where n is the number of vertices of a given graph. As its application, we develop an algorithm for generating all maximum cliques of a circular-arc graph. When the graph is given in the form of a family of n arcs on a circle, this algorithm runs in O(n3.5 + (output size)) time. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1016/0196-6774(92)90012-2 | J. Algorithms |
Keywords | Field | DocType |
maximum independent set,bipartite graph,circular-arc graph,maximum clique,technical report | Discrete mathematics,Combinatorics,Circulant graph,Line graph,Edge-transitive graph,Cubic graph,Simplex graph,Factor-critical graph,Mathematics,Voltage graph,Intersection number (graph theory) | Journal |
Volume | Issue | ISSN |
13 | 1 | 0196-6774 |
Citations | PageRank | References |
12 | 1.77 | 8 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Toshinobu Kashiwabara | 1 | 106 | 16.79 |
| Sumio Masuda | 2 | 150 | 20.26 |
| Kazuo Nakajima | 3 | 40 | 6.09 |
| Toshio Fujisawa | 4 | 92 | 15.13 |