234:
35:
3637:. He used this approach not only for 3-coloring but as part of a more general graph coloring algorithm, and similar approaches to graph coloring have been refined by other authors since. Other more complex problems can also be modeled as finding a clique or independent set of a specific type. This motivates the algorithmic problem of listing all maximal independent sets (or equivalently, all maximal cliques) efficiently.
192:
3641:
However, an algorithm with this time bound can be highly inefficient for graphs with more limited numbers of independent sets. For this reason, many researchers have studied algorithms that list all maximal independent sets in polynomial time per output set. The time per maximal independent set is proportional to that for
3085:: With a proper selection of the parameter δ in the partially parallel algorithm, it is possible to guarantee that it finishes after at most log(n) calls to the fully parallel algorithm, and the number of steps in each call is at most log(n). Hence the total run-time of the partially parallel algorithm is
3620:
An algorithm for listing all maximal independent sets or maximal cliques in a graph can be used as a subroutine for solving many NP-complete graph problems. Most obviously, the solutions to the maximum independent set problem, the maximum clique problem, and the minimum independent dominating problem
1096:
For every node u that is selected to S, the probability that u will be removed from S is at most 1/2. PROOF: This probability is at most the probability that a higher-neighbour of u is selected to S. For each higher-neighbour v, the probability that it is selected is at most 1/2d(v), which is at most
1083:
At least 1/2 of all edges are always good. PROOF: Build a directed version of G by directing each edge to the node with the higher degree (breaking ties arbitrarily). So for every bad node, the number of out-going edges is more than 2 times the number of in-coming edges. So every bad edge, that
637:
3640:
It is straightforward to turn a proof of Moon and Moser's 3 bound on the number of maximal independent sets into an algorithm that lists all such sets in time O(3). For graphs that have the largest possible number of maximal independent sets, this algorithm takes constant time per output set.
3785:. The many challenges of designing distributed parallel algorithms apply in equal to the maximum independent set problem. In particular, finding an algorithm that exhibits efficient runtime and is optimal in data communication for subdividing the graph and merging the independent set.
1208:/2 connected components, each with 2 nodes. The degree of all nodes is 1, so each node is selected with probability 1/2, and with probability 1/4 both nodes in a component are not chosen. Hence, the number of nodes drops by a factor of 4 each step, and the expected number of steps is
1092:
is selected. For each lower-neighbour v, the probability that it is not selected is (1-1/2d(v)), which is at most (1-1/2d(u)) (since d(u)>d(v)). The number of such neighbours is at least d(u)/3, since u is good. Hence the probability that no lower-neighbour is selected is at most
4287:
Distributed maximal independent set algorithms are strongly influenced by algorithms on the PRAM model. The original work by Luby and Alon et al. has led to several distributed algorithms. In terms of exchange of bits, these algorithms had a message size lower bound per round of
4323:
bits and would require additional characteristics of the graph. For example, the size of the graph would need to be known or the maximum degree of neighboring vertices for a given vertex could be queried. In 2010, Métivier et al. reduced the required message size per round to
3039:
Between the totally sequential and the totally parallel algorithms, there is a continuum of algorithms that are partly sequential and partly parallel. Given a fixed ordering on the nodes and a factor δ∈(0,1], the following algorithm returns the same MIS:
768:; because of their connection with Moon and Moser's bound, these graphs are also sometimes called Moon-Moser graphs. Tighter bounds are possible if one limits the size of the maximal independent sets: the number of maximal independent sets of size
3009:
Instead of randomizing in each step, it is possible to randomize once, at the beginning of the algorithm, by fixing a random ordering on the nodes. Given this fixed ordering, the following parallel algorithm achieves exactly the same MIS as the
706:
Certain graph families have also been characterized in terms of their maximal cliques or maximal independent sets. Examples include the maximal-clique irreducible and hereditary maximal-clique irreducible graphs. A graph is said to be
883:
683:, a set of vertices that includes at least one endpoint of each edge, and is minimal in the sense that none of its vertices can be removed while preserving the property that it is a cover. Minimal vertex covers have been studied in
1087:
For every good node u, the probability that a neighbour of u is selected to S is at least a certain positive constant. PROOF: the probability that NO neighbour of u is selected to S is at most the probability that none of u's
3769:
problem. Typically, the structure of the algorithm given follows other parallel graph algorithms - that is they subdivide the graph into smaller local problems that are solvable in parallel by running an identical algorithm.
1037:
For every edge in E, if both its endpoints are in the random set S, then remove from S the endpoint whose degree is lower (i.e. has fewer neighbours). Break ties arbitrarily, e.g. using a lexicographic order on the vertex
3621:
must all be maximal independent sets or maximal cliques, and can be found by an algorithm that lists all maximal independent sets or maximal cliques and retains the ones with the largest or smallest size. Similarly, the
495:
The above can be restated as a vertex either belongs to the independent set or has at least one neighbor vertex that belongs to the independent set. As a result, every edge of the graph has at least one endpoint not in
1100:
Hence, for every good node u, the probability that a neighbour of u is selected to S and remains in S is a certain positive constant. Hence, the probability that u is removed, in each step, is at least a positive
698:, a set of vertices such that every vertex in the graph either belongs to the set or is adjacent to the set. A set of vertices is a maximal independent set if and only if it is an independent dominating set.
1280:
Note that in every step, the node with the smallest number in each connected component always enters I, so there is always some progress. In particular, in the worst-case of the previous algorithm (
3603:
2758:
1104:
Hence, for every good edge e, the probability that e is removed, in each step, is at least a positive constant. So the number of good edges drops by at least a constant factor each step.
3513:
3245:
2641:
2545:
441:
2818:
2119:
1994:
1365:
3362:
3923:
2946:
2887:
2577:
2461:
2397:
2276:
2186:
2154:
2066:
1699:
1587:
1555:
1202:
764:. Any maximal independent set in this graph is formed by choosing one vertex from each triangle. The complementary graph, with exactly 3 maximal cliques, is a special type of
3179:
3131:
1921:
1894:
4093:
3985:
3867:
1787:
1743:
1245:
3452:
3411:
2987:
1157:
222:
The phrase "maximal independent set" is also used to describe maximal subsets of independent elements in mathematical structures other than graphs, and in particular in
4321:
4132:
733:
can be characterized as graphs in which every maximal clique intersects every maximal independent set, and in which the same property is true in all induced subgraphs.
4247:
4021:
1034:
Choose a random set of vertices S ⊆ V, by selecting each vertex v independently with probability 1/(2d(v)), where d is the degree of v (the number of neighbours of v).
3292:
317:
4277:
4182:
4051:
3825:
3763:
3725:
399:
370:
2673:
1523:
1461:
1429:
1397:
665:
4351:
4211:
2426:
2365:
2244:
2215:
470:
2848:
1491:
1084:
enters a node v, can be matched to a distinct set of two edges that exit the node v. Hence the total number of edges is at least 2 times the number of bad edges.
782:
4152:
3943:
2481:
2336:
2316:
2296:
2034:
2014:
1941:
1867:
1847:
1827:
1807:
1667:
1647:
1627:
1607:
1312:
576:
556:
534:
514:
490:
340:
756:
vertices also has at most 3 maximal independent sets. A graph with exactly 3 maximal independent sets is easy to construct: simply take the disjoint union of
5482:
Liang, Y. D.; Dhall, S. K.; Lakshmivarahan, S. (1991), "On the problem of finding all maximum weight independent sets in interval and circular arc graphs",
204:
graphs are maximal independent sets while the bottom two are independent sets, but not maximal. The maximum independent set is represented by the top left.
4023:
processors. Shortly after, Luby and Alon et al. independently improved on this result, bringing the maximal independent set problem into the realm of
1268:
If r(v) is smaller than the numbers of all neighbours of v, then v inserts itself into I, removes itself from V and tells its neighbours about this;
5820:
5683:
Tomita, E.; Tanaka, A.; Takahashi, H. (2006), "The worst-case time complexity for generating all maximal cliques and computational experiments",
891:
Certain families of graphs may, however, have much more restrictive bounds on the numbers of maximal independent sets or maximal cliques. If all
19:
This article is about the combinatorial aspects of maximal independent sets of vertices in a graph. For stronger notion with a similar name, see
5729:
Weigt, Martin; Hartmann, Alexander K. (2001), "Minimal vertex covers on finite-connectivity random graphs: A hard-sphere lattice-gas picture",
4465:
4454:
4587:
5185:
3629:
observed that listing maximal independent sets can also be used to find 3-colorings of graphs: a graph can be 3-colored if and only if the
4937:
Alon, Noga; Laszlo, Babai; Alon, Itai (1986). "A fast and simple randomized parallel algorithm for the maximal independent set problem".
5032:
Métivier, Y.; Robson, J. M.; Saheb-Djahromi, N.; Zemmari, A. (2010). "An optimal bit complexity randomized distributed MIS algorithm".
4654:
Blelloch, Guy; Fineman, Jeremy; Shun, Julian (2012). "Greedy
Sequential Maximal Independent Set and Matching are Parallel on Average".
4619:
Métivier, Y.; Robson, J. M.; Saheb-Djahromi, N.; Zemmari, A. (2010). "An optimal bit complexity randomized distributed MIS algorithm".
1869:. Recall that each node is given a random number in the same range. In a simple example with two disjoint nodes, each has probability
899:) edges, and if every subgraph of a graph in the family also belongs to the family, then each graph in the family can have at most O(
5461:
Leung, J. Y.-T. (1984), "Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs",
1255:
The following algorithm is better than the previous one in that at least one new node is always added in each connected component:
3793:
It was shown in 1984 by Karp et al. that a deterministic parallel solution on PRAM to the maximal independent set belonged in the
915: − 6 edges, and a subgraph of a planar graph is always planar, from which it follows that each planar graph has O(
208:
A graph may have many MISs of widely varying sizes; the largest, or possibly several equally large, MISs of a graph is called a
5708:
Tsukiyama, S.; Ide, M.; Ariyoshi, H.; Shirakawa, I. (1977), "A new algorithm for generating all the maximal independent sets",
5685:
1097:
1/2d(u) (since d(v)>d(u)). By union bound, the probability that no higher-neighbour is selected is at most d(u)/2d(u) = 1/2.
5582:
5543:
4981:
3518:
633:
Some authors include maximality as part of the definition of a clique, and refer to maximal cliques simply as cliques.
2678:
5558:
5554:
5499:
5116:
28:
5353:
Jennings, E.; Motycková, L. (1992), "A distributed algorithm for finding all maximal cliques in a network graph",
3658:
74:
outside the independent set that may join it because it is maximal with respect to the independent set property.
184:
in the graph, and every dominating set that is independent must be maximal independent, so MISs are also called
5177:
3774:
3460:
3192:
2582:
2486:
715:
if the same property is true for every induced subgraph. Hereditary maximal-clique irreducible graphs include
405:
320:
63:
24:
4428:
Luby’s
Algorithm, in: Lecture Notes for Randomized Algorithms, Last Updated by Eric Vigoda on February 2, 2006
3945:
is the vertex set size. In the same paper, a randomized parallel solution was also provided with a runtime of
3661:. The problem asks, given an undirected graph, how many maximal independent sets it contains. This problem is
5815:
5606:
5269:
3654:
2763:
2071:
1946:
1317:
1107:
Since at least half the edges are good, the total number of edges also drops by a constant factor each step.
3615:
3316:
4694:
675:
of a maximal independent set, that is, the set of vertices not belonging to the independent set, forms a
4919:
Karp, R.M.; Wigderson, A. (1984). "A fast parallel algorithm for the maximal independent set problem".
3872:
2895:
5565:
Mishra, N.; Pitt, L. (1997), "Generating all maximal independent sets of bounded-degree hypergraphs",
5164:
2853:
2550:
2434:
2370:
2249:
2159:
2127:
2039:
1672:
1560:
1528:
1166:
4902:
4819:
3672:
The problem is however tractable on some specific classes of graphs, for instance it is tractable on
3630:
3136:
3088:
142:
is independent, but is not maximal independent, because it is a subset of the larger independent set
5659:
5209:
5052:
4559:
4462:
4451:
1899:
1872:
5526:
5092:
4056:
3948:
3830:
4249:
processors. Today, it remains an open question as to if the maximal independent set problem is in
1748:
1704:
1211:
5015:
4594:
3732:
672:
610:, and that is not a subset of the vertices of any larger complete subgraph. That is, it is a set
516:. However, it is not true that every edge of the graph has at least one, or even one endpoint in
249:
show how vastly different in size two maximal independent sets (the right being maximum) can be.
209:
20:
3416:
3375:
2951:
1121:
903:) maximal cliques, all of which have size O(1). For instance, these conditions are true for the
5654:
5521:
5370:
5308:
Euler, R. (2005), "The
Fibonacci number of a grid graph and a new class of integer sequences",
5204:
5087:
5082:
Bomze, I. M.; Budinich, M.; Pardalos, P. M.; Pelillo, M. (1999), "The maximum clique problem",
4554:
4291:
4098:
626:. A graph may have many maximal cliques, of varying sizes; finding the largest of these is the
5784:
Yu, C.-W.; Chen, G.-H. (1993), "Generate all maximal independent sets in permutation graphs",
4216:
3990:
3454:
steps (since the longest path is a worst-case bound on the number of steps in that algorithm).
2431:
In each iteration of step 2, in expectation, half the edges are removed. PROOF: If the event
3778:
3642:
3369:
3262:
3252:
684:
667:, on the graph complement. Right is a vertex cover on the maximal independent set complement.
284:
71:
4781:"The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected"
4252:
4157:
4026:
3800:
3738:
3700:
378:
349:
5748:
5629:
5317:
5292:
3622:
3024:
Let W be the set of vertices in V with no earlier neighbours (based on the fixed ordering);
2646:
1496:
1434:
1402:
1370:
878:{\displaystyle \lfloor n/k\rfloor ^{k-(n{\bmod {k}})}\lfloor n/k+1\rfloor ^{n{\bmod {k}}}.}
643:
4903:"LITERATURE REVIEW: Parallel algorithms for the maximal independent set problem in graphs"
4327:
4187:
3079:
gives the totally sequential algorithm; setting δ=1 gives the totally parallel algorithm.
3066:
Remove from V all the nodes in the prefix P, and all the neighbours of nodes in the set W.
2675:, the expected number of edges removed due to one of these nodes having smallest value is
2402:
2341:
2220:
2191:
446:
8:
5668:
3697:; however, it has been shown that a deterministic parallel solution could be given by an
2823:
1466:
955:
716:
254:
238:
5752:
5520:, Lecture Notes in Computer Science, vol. 3111, Springer-Verlag, pp. 260–272,
5321:
4545:
Luby, M. (1986). "A Simple
Parallel Algorithm for the Maximal Independent Set Problem".
42:
has six different independent sets (two of them are maximum), shown as the red vertices.
5772:
5738:
5672:
5633:
5588:
5505:
5449:
5426:
5366:
5329:
5296:
5252:
5234:
5194:
5147:
5068:
4880:
4655:
4636:
4137:
3928:
3690:
2850:
edges removed every step, but each edge is counted twice (once per direction), giving
2466:
2321:
2301:
2281:
2019:
1999:
1926:
1852:
1832:
1812:
1792:
1652:
1632:
1612:
1592:
1297:
561:
541:
519:
499:
475:
325:
216:
2483:
are removed; hence the expected number of edges removed due to this event is at least
5764:
5578:
5550:
5539:
5509:
5495:
5474:
5427:"Generating all maximal independent sets: NP-hardness and polynomial time algorithms"
5422:
5410:
5386:
5357:, Lecture Notes in Computer Science, vol. 583, Springer-Verlag, pp. 281–293
5300:
5151:
5112:
4977:
4950:
4839:
4835:
4800:
979:
Given a Graph G(V,E), it is easy to find a single MIS using the following algorithm:
5776:
5676:
5453:
4884:
4640:
4427:
5793:
5756:
5717:
5694:
5664:
5637:
5615:
5592:
5570:
5531:
5487:
5470:
5441:
5406:
5382:
5362:
5341:
5278:
5256:
5244:
5214:
5139:
4969:
4946:
4870:
4831:
4792:
4628:
4564:
3782:
3766:
3372:
the longest path in the directed graph determined by the fixed ordering has length
959:
603:
599:
5516:
Makino, K.; Uno, T. (2004), "New algorithms for enumerating all maximal cliques",
1284:/2 connected components with 2 nodes each), a MIS will be found in a single step.
1064:(whose degree is higher than the degree of v), breaking ties as in the algorithm.
5625:
5535:
5288:
5127:
4999:
4469:
4458:
4154:
is the number of edges in the graph. In order to show that their algorithm is in
3794:
3666:
3634:
720:
711:
if every maximal clique has an edge that belongs to no other maximal clique, and
215:. The graphs in which all maximal independent sets have the same size are called
39:
5229:(2005), "All maximal independent sets and dynamic dominance for sparse graphs",
3689:
The maximal independent set problem was originally thought to be non-trivial to
5760:
5226:
5173:
5106:
4386:
1271:
If v heard that one of its neighbours got into I, then v removes itself from V.
920:
749:
724:
695:
627:
607:
181:
5797:
5699:
5108:
Proceedings of the
Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms
4632:
3693:
due to the fact that the lexicographical maximal independent set proved to be
765:
5809:
5491:
5418:
5394:
4843:
4804:
963:
947:
924:
5264:
5248:
4973:
4780:
4353:, which is optimal and removed the need for any additional graph knowledge.
1896:
of being smallest. If there are three disjoint nodes, each has probability
34:
5768:
5345:
932:
904:
688:
680:
223:
47:
5574:
4875:
4858:
5743:
3773:
Initial research into the maximal independent set problem started on the
3728:
943:
761:
5073:
5620:
5283:
5218:
4509:
3694:
3625:
can be found as the complement of one of the maximal independent sets.
578:
because these vertices are disjoint by the independent set definition.
87:
5332:(1987), "The number of maximal independent sets in connected graphs",
5239:
5199:
3679:
1071:
if more than 2/3 of its neighbors are higher neighbours. Call an edge
962:. Therefore, both numbers are proportional to powers of 1.324718, the
5601:
3827:. That is to say, their algorithm finds a maximal independent set in
3133:. Hence the run-time of the fully parallel algorithm is also at most
5721:
5445:
5397:(1976), "A note on the complexity of the chromatic number problem",
5143:
4796:
4568:
2036:, so a node becomes double counted. Using the same logic, the event
691:
model, a mathematical abstraction of fluid-solid state transitions.
23:. For other aspects of independent vertex sets in graph theory, see
5031:
4618:
636:
233:
191:
5645:
Stix, V. (2004), "Finding all maximal cliques in dynamic graphs",
4660:
1367:
of being removed. PROOF: For each edge connecting a pair of nodes
16:
Independent set which is not a subset of any other independent set
4818:
Corneil, D. G.; Lerchs, H.; Burlingham, L. Stewart (1981-07-01).
3673:
730:
227:
5231:
Proc. Sixteenth Annual ACM-SIAM Symposium on
Discrete Algorithms
5178:"Small maximal independent sets and faster exact graph coloring"
3657:
associated to maximal independent sets has been investigated in
3645:
in dense graphs, or faster in various classes of sparse graphs.
1265:
Selects a random number r(v) in and sends it to its neighbours;
5355:
Proc. First Latin
American Symposium on Theoretical Informatics
3662:
3515:, then WHP the run-time of the partially parallel algorithm is
67:
5361:
4722:
3030:
Remove from V the nodes in the set W and all their neighbours.
5707:
4746:
2318:
are also removed. The number of outgoing directed edges from
1044:
Remove from V the set S and all the neighbours of nodes in S.
861:
818:
258:
5081:
4710:
4184:, they initially presented a randomized algorithm that uses
2246:
directed outgoing edges, respectively. PROOF: In the event
1996:
of being smallest because it is possible that a neighbor of
1163:
A worst-case graph, in which the average number of steps is
538:
Notice that any neighbor to a vertex in the independent set
969:
5086:, vol. 4, Kluwer Academic Publishers, pp. 1–74,
70:
of any other independent set. In other words, there is no
5053:"Counting non-isomorphic maximal independent sets of the
3060:
Let W be a MIS on P using the totally parallel algorithm.
2993:
266:
5481:
5417:
4730:
4726:
4504:. Chiba and Nishizeki express the condition of having O(
4213:
processors but could be derandomized with an additional
2579:, i.e. the expected number of edges removed is at least
1493:
is now twice as large. For every pair of directed edges
888:
The graphs achieving this bound are again Turán graphs.
4817:
4372:
shows that the number of different sizes of MISs in an
3609:
1004:
640:
Left is a maximal independent set. Middle is a clique,
5373:(1988), "On generating all maximal independent sets",
5130:(1985), "Arboricity and subgraph listing algorithms",
1262:
While V is not empty, each node v does the following:
5682:
5518:
5484:
Proceeding of the 1991 Symposium on
Applied Computing
4698:
4330:
4294:
4255:
4219:
4190:
4160:
4140:
4101:
4059:
4029:
3993:
3951:
3931:
3875:
3833:
3803:
3741:
3703:
3521:
3463:
3419:
3378:
3319:
3265:
3195:
3139:
3091:
2954:
2898:
2856:
2826:
2766:
2681:
2649:
2585:
2553:
2489:
2469:
2437:
2405:
2373:
2344:
2324:
2304:
2284:
2252:
2223:
2194:
2162:
2130:
2074:
2042:
2022:
2002:
1949:
1929:
1902:
1875:
1855:
1835:
1815:
1795:
1751:
1707:
1675:
1655:
1635:
1615:
1595:
1563:
1531:
1499:
1469:
1437:
1405:
1373:
1320:
1300:
1250:
1214:
1169:
1124:
1075:
if both its endpoints are bad; otherwise the edge is
785:
646:
564:
544:
522:
502:
478:
449:
408:
381:
352:
328:
287:
154:
In this same graph, the maximal cliques are the sets
4966:
Distributed
Computing: A Locality-Sensitive Approach
4779:
Provan, J. Scott; Ball, Michael O. (November 1983).
3648:
3309:
If, in any step, the degree of each node is at most
590:
is a maximal independent set in some graph, it is a
4653:
3680:
Parallelization of finding maximum independent sets
3665:-hard already when the input is restricted to be a
3457:Combining these two facts gives that, if we select
3413:. Hence the fully parallel algorithm takes at most
3251:is the maximum degree of a node in the graph, then
5105:-colouring and finding maximal independent sets",
4345:
4315:
4282:
4271:
4241:
4205:
4176:
4146:
4126:
4087:
4045:
4015:
3979:
3937:
3917:
3861:
3819:
3757:
3719:
3597:
3507:
3446:
3405:
3356:
3298:) steps, all remaining nodes have degree 0 (since
3286:
3239:
3173:
3125:
2981:
2940:
2881:
2842:
2812:
2752:
2667:
2635:
2571:
2539:
2475:
2455:
2420:
2391:
2359:
2330:
2310:
2290:
2270:
2238:
2209:
2180:
2148:
2113:
2060:
2028:
2008:
1988:
1935:
1915:
1888:
1861:
1841:
1821:
1801:
1781:
1737:
1693:
1661:
1641:
1621:
1601:
1581:
1549:
1517:
1485:
1455:
1423:
1391:
1359:
1306:
1239:
1196:
1151:
1020:The following algorithm finds a MIS in time O(log
877:
659:
570:
550:
528:
508:
484:
464:
435:
393:
364:
334:
311:
5352:
4718:
4588:"Principles of Distributed Computing (lecture 7)"
3616:Clique problem § Listing all maximal cliques
3598:{\displaystyle O(\log(D)\log(n))=O(\log ^{2}(n))}
2892:Hence, the expected run time of the algorithm is
1060:(whose degree is lower than the degree of v) and
931:maximal cliques, even though they are not always
752:maximal cliques. Complementarily, any graph with
701:
5807:
5050:
4521:
2753:{\displaystyle {\frac {d(w)+d(v)}{d(w)+d(v)}}=1}
995:Remove from V the node v and all its neighbours.
950:, and the number of maximal independent sets in
618:is connected by an edge and every vertex not in
5567:Proc. Tenth Conf. Computational Learning Theory
4921:Proc. 16th ACM Symposium on Theory of Computing
1399:, replace it with two directed edges, one from
5125:
5051:Bisdorff, Raymond; Marichal, Jean-Luc (2008),
4997:Lynch, N.A. (1996). "Distributed Algorithms".
4936:
4723:Johnson, Yannakakis & Papadimitriou (1988)
4501:
4450:Information System on Graph Class Inclusions:
3777:and has since expanded to produce results for
736:
5728:
5159:Croitoru, C. (1979), "On stables in graphs",
4918:
4438:
1056:: For each node v, divide its neighbours to
622:is missing an edge to at least one vertex in
602:. A maximal clique is a set of vertices that
5186:Journal of Graph Algorithms and Applications
4463:hereditary maximal clique irreducible graphs
895:-vertex graphs in a family of graphs have O(
853:
832:
801:
786:
5647:Computational Optimization and Applications
4693:. For a matching bound for the widely used
4512:of the graphs in the family being constant.
3057:nodes that are first in the fixed ordering.
1118:is the number of edges. This is bounded by
27:. For other kinds of independent sets, see
5564:
4778:
4738:
4582:
4580:
4578:
3633:of one of its maximal independent sets is
938:The number of maximal independent sets in
919:) maximal cliques (of size at most four).
5742:
5698:
5658:
5619:
5599:
5525:
5515:
5282:
5238:
5208:
5198:
5091:
5072:
4874:
4859:"An overview of computational complexity"
4762:
4734:
4659:
4558:
3508:{\displaystyle \delta =2^{i}\log {(n)}/D}
3240:{\displaystyle \delta =2^{i}\log {(n)}/D}
3011:
2636:{\displaystyle {\frac {d(v)}{d(w)+d(v)}}}
2547:. The same is true for the reverse event
2540:{\displaystyle {\frac {d(w)}{d(v)+d(w)}}}
741:
436:{\displaystyle N(v)\cap S\neq \emptyset }
5225:
5172:
5158:
4766:
4731:Liang, Dhall & Lakshmivarahan (1991)
4727:Lawler, Lenstra & Rinnooy Kan (1980)
4714:
4690:
4674:
4489:
4485:
2889:edges removed in expectation every step.
970:Finding a single maximal independent set
635:
232:
190:
134:are both maximally independent. The set
33:
5013:
4575:
3306:), and can be removed in a single step.
2813:{\displaystyle \sum _{{v,w}\in E}1=|E|}
974:
5821:Computational problems in graph theory
5808:
5783:
5393:
5328:
5167:, Cluj-Napoca, Romania, pp. 55–60
5101:Byskov, J. M. (2003), "Algorithms for
5100:
5084:Handbook of Combinatorial Optimization
4750:
4678:
4540:
4538:
4529:
4508:) edges equivalently, in terms of the
4481:
3626:
2994:Random-permutation parallel algorithm
2114:{\displaystyle {\frac {1}{d(w)+d(v)}}}
1989:{\displaystyle {\frac {1}{d(v)+d(w)}}}
1360:{\displaystyle {\frac {1}{d(v)+d(w)}}}
581:
5460:
5307:
5263:
5161:Proc. Third Coll. Operations Research
4996:
4963:
4932:
4930:
4900:
4896:
4894:
4699:Tomita, Tanaka & Takahashi (2006)
4525:
4369:
3357:{\displaystyle \delta =C\log {(n)}/d}
713:hereditary maximal-clique irreducible
5644:
5016:"Chapter 4: Maximal Independent Set"
4856:
4742:
4544:
4423:
4421:
3610:Listing all maximal independent sets
3014:(i.e. the result is deterministic):
1110:Hence, the number of steps is O(log
1005:Random-selection parallel algorithm
614:such that every pair of vertices in
4535:
3788:
2643:. Hence, for every undirected edge
694:Every maximal independent set is a
13:
5669:10.1023/B:COAP.0000008651.28952.b6
4927:
4891:
4484:. For related earlier results see
2298:is removed, all neighboring nodes
1923:of being smallest. In the case of
1251:Random-priority parallel algorithm
1170:
911:-vertex planar graph has at most 3
430:
14:
5832:
5233:, vol. 5, pp. 451–459,
4452:maximal clique irreducible graphs
4418:
4376:-vertex graph may be as large as
3918:{\displaystyle O((n/\log n)^{3})}
3649:Counting maximal independent sets
2941:{\displaystyle 3\log _{4/3}(m)+1}
5604:(1965), "On cliques in graphs",
5425:; Rinnooy Kan, A. H. G. (1980),
5267:(1966), "On cliques in graphs",
2882:{\displaystyle {\frac {|E|}{2}}}
2572:{\displaystyle (w\rightarrow v)}
2456:{\displaystyle (v\rightarrow w)}
2392:{\displaystyle (w\rightarrow v)}
2271:{\displaystyle (v\rightarrow w)}
2181:{\displaystyle (w\rightarrow v)}
2149:{\displaystyle (v\rightarrow w)}
2061:{\displaystyle (w\rightarrow v)}
1694:{\displaystyle (v\rightarrow w)}
1582:{\displaystyle (w\rightarrow v)}
1550:{\displaystyle (v\rightarrow w)}
1197:{\displaystyle \Theta (\log(n))}
372:, one of the following is true:
29:Independent set (disambiguation)
5025:
5007:
4990:
4957:
4912:
4850:
4811:
4772:
4756:
4719:Jennings & Motycková (1992)
4704:
4684:
4668:
4647:
4612:
4283:Communication and data exchange
3659:computational complexity theory
3255:all nodes remaining after step
3174:{\displaystyle O(\log ^{2}(n))}
3126:{\displaystyle O(\log ^{2}(n))}
2463:happens then all neighbours of
2068:also has probability at least
1943:, it has probability at least
679:. That is, the complement is a
5399:Information Processing Letters
5375:Information Processing Letters
5111:, Soda '03, pp. 456–457,
4522:Bisdorff & Marichal (2008)
4515:
4495:
4475:
4444:
4432:
4363:
4340:
4334:
4310:
4298:
4236:
4223:
4200:
4194:
4121:
4105:
4082:
4063:
4010:
3997:
3974:
3955:
3912:
3903:
3882:
3879:
3856:
3837:
3592:
3589:
3583:
3567:
3558:
3555:
3549:
3540:
3534:
3525:
3493:
3487:
3441:
3438:
3432:
3423:
3400:
3397:
3391:
3382:
3342:
3336:
3225:
3219:
3168:
3165:
3159:
3143:
3120:
3117:
3111:
3095:
2976:
2973:
2967:
2958:
2929:
2923:
2869:
2861:
2836:
2828:
2820:, gives an expected number of
2806:
2798:
2738:
2732:
2723:
2717:
2709:
2703:
2694:
2688:
2662:
2650:
2627:
2621:
2612:
2606:
2598:
2592:
2566:
2560:
2554:
2531:
2525:
2516:
2510:
2502:
2496:
2450:
2444:
2438:
2415:
2409:
2386:
2380:
2374:
2354:
2348:
2265:
2259:
2253:
2233:
2227:
2204:
2198:
2175:
2169:
2163:
2143:
2137:
2131:
2105:
2099:
2090:
2084:
2055:
2049:
2043:
1980:
1974:
1965:
1959:
1916:{\displaystyle {\frac {1}{3}}}
1889:{\displaystyle {\frac {1}{2}}}
1776:
1770:
1761:
1755:
1732:
1726:
1717:
1711:
1688:
1682:
1676:
1576:
1570:
1564:
1544:
1538:
1532:
1512:
1500:
1479:
1471:
1450:
1438:
1418:
1406:
1386:
1374:
1351:
1345:
1336:
1330:
1234:
1228:
1191:
1188:
1182:
1173:
1146:
1143:
1137:
1128:
827:
811:
702:Graph family characterizations
459:
453:
418:
412:
306:
294:
25:Independent set (graph theory)
1:
5607:Israel Journal of Mathematics
5270:Israel Journal of Mathematics
5043:
4820:"Complement reducible graphs"
4088:{\displaystyle O(\log ^{2}n)}
3980:{\displaystyle O(\log ^{4}n)}
3862:{\displaystyle O(\log ^{4}n)}
3044:Initialize I to an empty set.
3018:Initialize I to an empty set.
1259:Initialize I to an empty set.
1028:Initialize I to an empty set.
983:Initialize I to an empty set.
276:
237:Two independent sets for the
5686:Theoretical Computer Science
5536:10.1007/978-3-540-27810-8_23
5475:10.1016/0196-6774(84)90037-3
5411:10.1016/0020-0190(76)90065-X
5387:10.1016/0020-0190(88)90065-8
5310:Journal of Integer Sequences
5061:Journal of Integer Sequences
4951:10.1016/0196-6774(86)90019-2
4901:Barba, Luis (October 2012).
4836:10.1016/0166-218X(81)90013-5
4824:Discrete Applied Mathematics
4593:. ETH Zurich. Archived from
4502:Chiba & Nishizeki (1985)
4356:
3181:. The main proof steps are:
1782:{\displaystyle r(v)<r(x)}
1738:{\displaystyle r(v)<r(w)}
1240:{\displaystyle \log _{4}(n)}
7:
4857:Cook, Stephen (June 1983).
4439:Weigt & Hartmann (2001)
744:showed that any graph with
737:Bounding the number of sets
186:independent dominating sets
10:
5837:
5786:Internat. J. Comput. Math.
5761:10.1103/PhysRevE.63.056127
3727:reduction from either the
3684:
3613:
3447:{\displaystyle O(\log(n))}
3406:{\displaystyle O(\log(n))}
2982:{\displaystyle O(\log(n))}
2760:. Summing over all edges,
1669:, respectively. The event
1152:{\displaystyle O(\log(n))}
709:maximal-clique irreducible
257:are associated with MISs:
77:For example, in the graph
18:
5798:10.1080/00207169308804157
5710:SIAM Journal on Computing
5700:10.1016/j.tcs.2006.06.015
5434:SIAM Journal on Computing
5132:SIAM Journal on Computing
4785:SIAM Journal on Computing
4633:10.1007/s00446-010-0121-5
4547:SIAM Journal on Computing
4395:and is never larger than
4316:{\displaystyle O(\log n)}
4127:{\displaystyle O(mn^{2})}
1314:has probability at least
776:-vertex graph is at most
596:maximal complete subgraph
472:denotes the neighbors of
5492:10.1109/SOAC.1991.143921
4739:Mishra & Pitt (1997)
4412:
4242:{\displaystyle O(n^{2})}
4016:{\displaystyle O(n^{2})}
3050:Select a factor δ∈(0,1].
2428:directed outgoing edges.
2016:is also the neighbor of
5334:Journal of Graph Theory
5249:10.1145/1597036.1597042
5165:Babeş-Bolyai University
4974:10.1137/1.9780898719772
4763:Makino & Uno (2004)
4747:Tsukiyama et al. (1977)
4735:Makino & Uno (2004)
4695:Bron–Kerbosch algorithm
3795:Nick's Class complexity
3287:{\displaystyle D/2^{i}}
2367:. With the same logic,
742:Moon & Moser (1965)
689:hard-sphere lattice gas
687:in connection with the
344:maximal independent set
312:{\displaystyle G=(V,E)}
52:maximal independent set
21:Maximum independent set
5346:10.1002/jgt.3190110403
4347:
4317:
4273:
4272:{\displaystyle NC_{1}}
4243:
4207:
4178:
4177:{\displaystyle NC_{2}}
4148:
4128:
4089:
4047:
4046:{\displaystyle NC_{2}}
4017:
3981:
3939:
3919:
3863:
3821:
3820:{\displaystyle NC_{4}}
3779:distributed algorithms
3759:
3758:{\displaystyle NC^{2}}
3721:
3720:{\displaystyle NC^{1}}
3599:
3509:
3448:
3407:
3358:
3288:
3241:
3175:
3127:
3047:While V is not empty:
3021:While V is not empty:
2983:
2942:
2883:
2844:
2814:
2754:
2669:
2637:
2573:
2541:
2477:
2457:
2422:
2393:
2361:
2332:
2312:
2292:
2272:
2240:
2211:
2182:
2150:
2115:
2062:
2030:
2010:
1990:
1937:
1917:
1890:
1863:
1843:
1823:
1803:
1783:
1739:
1695:
1663:
1649:pre-emptively removes
1643:
1623:
1609:pre-emptively removes
1603:
1583:
1551:
1519:
1487:
1457:
1425:
1393:
1361:
1308:
1241:
1198:
1153:
1031:While V is not empty:
986:While V is not empty:
879:
668:
661:
628:maximum clique problem
572:
552:
530:
510:
486:
466:
437:
395:
394:{\displaystyle v\in S}
366:
365:{\displaystyle v\in V}
336:
313:
250:
205:
43:
5575:10.1145/267460.267500
5463:Journal of Algorithms
5034:Distributed Computing
4964:Peleg, David (2000).
4939:Journal of Algorithms
4876:10.1145/358141.358144
4621:Distributed Computing
4348:
4318:
4274:
4244:
4208:
4179:
4149:
4129:
4090:
4048:
4018:
3982:
3940:
3920:
3864:
3822:
3760:
3722:
3643:matrix multiplication
3614:Further information:
3600:
3510:
3449:
3408:
3359:
3289:
3242:
3176:
3128:
3053:Let P be the set of δ
3012:#Sequential algorithm
2984:
2943:
2884:
2845:
2815:
2755:
2670:
2668:{\displaystyle (w,v)}
2638:
2574:
2542:
2478:
2458:
2423:
2394:
2362:
2333:
2313:
2293:
2273:
2241:
2212:
2183:
2151:
2116:
2063:
2031:
2011:
1991:
1938:
1918:
1891:
1864:
1844:
1824:
1804:
1784:
1740:
1696:
1664:
1644:
1624:
1604:
1584:
1552:
1525:, define two events:
1520:
1518:{\displaystyle (v,w)}
1488:
1458:
1456:{\displaystyle (w,v)}
1426:
1424:{\displaystyle (v,w)}
1394:
1392:{\displaystyle (v,w)}
1362:
1309:
1242:
1204:, is a graph made of
1199:
1154:
880:
748:vertices has at most
685:statistical mechanics
662:
660:{\displaystyle K_{3}}
639:
573:
553:
531:
511:
487:
467:
438:
396:
367:
337:
314:
271:MISs in a given graph
236:
194:
37:
5816:Graph theory objects
5569:, pp. 211–217,
5486:, pp. 465–470,
5371:Papadimitriou, C. H.
4751:Yu & Chen (1993)
4346:{\displaystyle O(1)}
4328:
4292:
4253:
4217:
4206:{\displaystyle O(m)}
4188:
4158:
4138:
4099:
4057:
4027:
3991:
3949:
3929:
3873:
3831:
3801:
3739:
3701:
3623:minimum vertex cover
3519:
3461:
3417:
3376:
3317:
3263:
3259:have degree at most
3193:
3137:
3089:
2952:
2896:
2854:
2824:
2764:
2679:
2647:
2583:
2551:
2487:
2467:
2435:
2421:{\displaystyle d(v)}
2403:
2371:
2360:{\displaystyle d(w)}
2342:
2322:
2302:
2282:
2250:
2239:{\displaystyle d(v)}
2221:
2210:{\displaystyle d(w)}
2192:
2160:
2128:
2072:
2040:
2020:
2000:
1947:
1927:
1900:
1873:
1853:
1833:
1813:
1793:
1749:
1705:
1673:
1653:
1633:
1613:
1593:
1561:
1529:
1497:
1467:
1435:
1403:
1371:
1318:
1298:
1212:
1167:
1122:
975:Sequential algorithm
783:
717:triangle-free graphs
677:minimal vertex cover
644:
562:
542:
520:
500:
476:
465:{\displaystyle N(v)}
447:
406:
379:
350:
326:
285:
263:MIS in a given graph
255:algorithmic problems
90:with three vertices
5753:2001PhRvE..63e6127W
5322:2005JIntS...8...26E
4711:Bomze et al. (1999)
4600:on 21 February 2015
3765:reduction from the
3729:maximum set packing
2843:{\displaystyle |E|}
2188:occur, they remove
1486:{\displaystyle |E|}
1041:Add the set S to I.
992:Add v to the set I;
600:complementary graph
582:Related vertex sets
217:well-covered graphs
5621:10.1007/BF02760024
5284:10.1007/BF02771637
5219:10.7155/jgaa.00064
4468:2007-07-08 at the
4457:2007-07-09 at the
4343:
4313:
4269:
4239:
4203:
4174:
4144:
4134:processors, where
4124:
4085:
4043:
4013:
3977:
3935:
3915:
3859:
3817:
3755:
3717:
3595:
3505:
3444:
3403:
3364:(for any constant
3354:
3294:. Thus, after log(
3284:
3237:
3171:
3123:
2979:
2938:
2879:
2840:
2810:
2790:
2750:
2665:
2633:
2569:
2537:
2473:
2453:
2418:
2389:
2357:
2328:
2308:
2288:
2268:
2236:
2207:
2178:
2146:
2111:
2058:
2026:
2006:
1986:
1933:
1913:
1886:
1859:
1839:
1819:
1799:
1779:
1735:
1691:
1659:
1639:
1619:
1599:
1579:
1547:
1515:
1483:
1453:
1421:
1389:
1357:
1304:
1237:
1194:
1149:
989:Choose a node v∈V;
927:also have at most
875:
669:
657:
568:
548:
526:
506:
482:
462:
433:
391:
362:
332:
309:
251:
206:
60:maximal stable set
44:
5584:978-0-89791-891-6
5545:978-3-540-22339-9
4983:978-0-89871-464-7
4147:{\displaystyle m}
3938:{\displaystyle n}
3783:computer clusters
3735:problem or by an
2877:
2767:
2742:
2631:
2535:
2476:{\displaystyle w}
2331:{\displaystyle w}
2311:{\displaystyle w}
2291:{\displaystyle v}
2121:of being removed.
2109:
2029:{\displaystyle w}
2009:{\displaystyle v}
1984:
1936:{\displaystyle v}
1911:
1884:
1862:{\displaystyle w}
1842:{\displaystyle x}
1822:{\displaystyle v}
1809:is a neighbor of
1802:{\displaystyle w}
1662:{\displaystyle v}
1642:{\displaystyle w}
1622:{\displaystyle w}
1602:{\displaystyle v}
1355:
1307:{\displaystyle v}
1062:higher neighbours
608:complete subgraph
571:{\displaystyle S}
551:{\displaystyle S}
529:{\displaystyle S}
509:{\displaystyle S}
485:{\displaystyle v}
335:{\displaystyle S}
40:graph of the cube
5828:
5800:
5779:
5746:
5744:cond-mat/0011446
5724:
5703:
5702:
5679:
5662:
5640:
5623:
5595:
5548:
5529:
5512:
5477:
5456:
5431:
5413:
5389:
5358:
5348:
5324:
5303:
5286:
5259:
5242:
5221:
5212:
5202:
5182:
5168:
5154:
5121:
5096:
5095:
5077:
5076:
5038:
5037:
5029:
5023:
5022:
5020:
5014:Wattenhofer, R.
5011:
5005:
5004:
4994:
4988:
4987:
4961:
4955:
4954:
4934:
4925:
4924:
4916:
4910:
4909:
4907:
4898:
4889:
4888:
4878:
4854:
4848:
4847:
4815:
4809:
4808:
4776:
4770:
4760:
4754:
4708:
4702:
4688:
4682:
4672:
4666:
4665:
4663:
4651:
4645:
4644:
4616:
4610:
4609:
4607:
4605:
4599:
4592:
4584:
4573:
4572:
4562:
4553:(4): 1036–1053.
4542:
4533:
4519:
4513:
4499:
4493:
4479:
4473:
4448:
4442:
4436:
4430:
4425:
4406:
4404:
4394:
4375:
4367:
4352:
4350:
4349:
4344:
4322:
4320:
4319:
4314:
4278:
4276:
4275:
4270:
4268:
4267:
4248:
4246:
4245:
4240:
4235:
4234:
4212:
4210:
4209:
4204:
4183:
4181:
4180:
4175:
4173:
4172:
4153:
4151:
4150:
4145:
4133:
4131:
4130:
4125:
4120:
4119:
4094:
4092:
4091:
4086:
4075:
4074:
4052:
4050:
4049:
4044:
4042:
4041:
4022:
4020:
4019:
4014:
4009:
4008:
3986:
3984:
3983:
3978:
3967:
3966:
3944:
3942:
3941:
3936:
3924:
3922:
3921:
3916:
3911:
3910:
3892:
3868:
3866:
3865:
3860:
3849:
3848:
3826:
3824:
3823:
3818:
3816:
3815:
3789:Complexity class
3767:2-satisfiability
3764:
3762:
3761:
3756:
3754:
3753:
3733:maximal matching
3726:
3724:
3723:
3718:
3716:
3715:
3655:counting problem
3604:
3602:
3601:
3596:
3579:
3578:
3514:
3512:
3511:
3506:
3501:
3496:
3479:
3478:
3453:
3451:
3450:
3445:
3412:
3410:
3409:
3404:
3363:
3361:
3360:
3355:
3350:
3345:
3313:, and we select
3293:
3291:
3290:
3285:
3283:
3282:
3273:
3246:
3244:
3243:
3238:
3233:
3228:
3211:
3210:
3180:
3178:
3177:
3172:
3155:
3154:
3132:
3130:
3129:
3124:
3107:
3106:
3006:
3005:
3001:
2988:
2986:
2985:
2980:
2947:
2945:
2944:
2939:
2919:
2918:
2914:
2888:
2886:
2885:
2880:
2878:
2873:
2872:
2864:
2858:
2849:
2847:
2846:
2841:
2839:
2831:
2819:
2817:
2816:
2811:
2809:
2801:
2789:
2782:
2759:
2757:
2756:
2751:
2743:
2741:
2712:
2683:
2674:
2672:
2671:
2666:
2642:
2640:
2639:
2634:
2632:
2630:
2601:
2587:
2578:
2576:
2575:
2570:
2546:
2544:
2543:
2538:
2536:
2534:
2505:
2491:
2482:
2480:
2479:
2474:
2462:
2460:
2459:
2454:
2427:
2425:
2424:
2419:
2398:
2396:
2395:
2390:
2366:
2364:
2363:
2358:
2337:
2335:
2334:
2329:
2317:
2315:
2314:
2309:
2297:
2295:
2294:
2289:
2277:
2275:
2274:
2269:
2245:
2243:
2242:
2237:
2216:
2214:
2213:
2208:
2187:
2185:
2184:
2179:
2155:
2153:
2152:
2147:
2124:When the events
2120:
2118:
2117:
2112:
2110:
2108:
2076:
2067:
2065:
2064:
2059:
2035:
2033:
2032:
2027:
2015:
2013:
2012:
2007:
1995:
1993:
1992:
1987:
1985:
1983:
1951:
1942:
1940:
1939:
1934:
1922:
1920:
1919:
1914:
1912:
1904:
1895:
1893:
1892:
1887:
1885:
1877:
1868:
1866:
1865:
1860:
1848:
1846:
1845:
1840:
1828:
1826:
1825:
1820:
1808:
1806:
1805:
1800:
1788:
1786:
1785:
1780:
1744:
1742:
1741:
1736:
1700:
1698:
1697:
1692:
1668:
1666:
1665:
1660:
1648:
1646:
1645:
1640:
1628:
1626:
1625:
1620:
1608:
1606:
1605:
1600:
1588:
1586:
1585:
1580:
1556:
1554:
1553:
1548:
1524:
1522:
1521:
1516:
1492:
1490:
1489:
1484:
1482:
1474:
1462:
1460:
1459:
1454:
1430:
1428:
1427:
1422:
1398:
1396:
1395:
1390:
1366:
1364:
1363:
1358:
1356:
1354:
1322:
1313:
1311:
1310:
1305:
1246:
1244:
1243:
1238:
1224:
1223:
1203:
1201:
1200:
1195:
1158:
1156:
1155:
1150:
1090:lower neighbours
1058:lower neighbours
1017:
1016:
1012:
960:Padovan sequence
958:is given by the
946:is given by the
884:
882:
881:
876:
871:
870:
869:
868:
842:
831:
830:
826:
825:
796:
721:bipartite graphs
666:
664:
663:
658:
656:
655:
577:
575:
574:
569:
557:
555:
554:
549:
535:
533:
532:
527:
515:
513:
512:
507:
491:
489:
488:
483:
471:
469:
468:
463:
442:
440:
439:
434:
400:
398:
397:
392:
371:
369:
368:
363:
341:
339:
338:
333:
318:
316:
315:
310:
248:
203:
180:A MIS is also a
177:
165:
153:
141:
133:
121:
113:
112:
107:
106:
102:, and two edges
101:
97:
93:
85:
5836:
5835:
5831:
5830:
5829:
5827:
5826:
5825:
5806:
5805:
5804:
5722:10.1137/0206036
5660:10.1.1.497.6424
5585:
5546:
5502:
5446:10.1137/0209042
5429:
5210:10.1.1.342.4049
5180:
5144:10.1137/0214017
5119:
5074:math.CO/0701647
5046:
5041:
5030:
5026:
5018:
5012:
5008:
5000:Morgan Kaufmann
4995:
4991:
4984:
4962:
4958:
4935:
4928:
4917:
4913:
4905:
4899:
4892:
4855:
4851:
4816:
4812:
4797:10.1137/0212053
4777:
4773:
4767:Eppstein (2005)
4761:
4757:
4715:Eppstein (2005)
4709:
4705:
4691:Eppstein (2003)
4689:
4685:
4675:Eppstein (2003)
4673:
4669:
4652:
4648:
4617:
4613:
4603:
4601:
4597:
4590:
4586:
4585:
4576:
4569:10.1137/0215074
4560:10.1.1.225.5475
4543:
4536:
4520:
4516:
4500:
4496:
4490:Eppstein (2003)
4486:Croitoru (1979)
4480:
4476:
4470:Wayback Machine
4459:Wayback Machine
4449:
4445:
4437:
4433:
4426:
4419:
4415:
4410:
4409:
4396:
4377:
4373:
4368:
4364:
4359:
4329:
4326:
4325:
4293:
4290:
4289:
4285:
4263:
4259:
4254:
4251:
4250:
4230:
4226:
4218:
4215:
4214:
4189:
4186:
4185:
4168:
4164:
4159:
4156:
4155:
4139:
4136:
4135:
4115:
4111:
4100:
4097:
4096:
4070:
4066:
4058:
4055:
4054:
4037:
4033:
4028:
4025:
4024:
4004:
4000:
3992:
3989:
3988:
3962:
3958:
3950:
3947:
3946:
3930:
3927:
3926:
3906:
3902:
3888:
3874:
3871:
3870:
3844:
3840:
3832:
3829:
3828:
3811:
3807:
3802:
3799:
3798:
3791:
3749:
3745:
3740:
3737:
3736:
3711:
3707:
3702:
3699:
3698:
3687:
3682:
3667:bipartite graph
3651:
3618:
3612:
3574:
3570:
3520:
3517:
3516:
3497:
3486:
3474:
3470:
3462:
3459:
3458:
3418:
3415:
3414:
3377:
3374:
3373:
3346:
3335:
3318:
3315:
3314:
3278:
3274:
3269:
3264:
3261:
3260:
3229:
3218:
3206:
3202:
3194:
3191:
3190:
3150:
3146:
3138:
3135:
3134:
3102:
3098:
3090:
3087:
3086:
3007:
3003:
2999:
2997:
2996:
2953:
2950:
2949:
2910:
2906:
2902:
2897:
2894:
2893:
2868:
2860:
2859:
2857:
2855:
2852:
2851:
2835:
2827:
2825:
2822:
2821:
2805:
2797:
2772:
2771:
2765:
2762:
2761:
2713:
2684:
2682:
2680:
2677:
2676:
2648:
2645:
2644:
2602:
2588:
2586:
2584:
2581:
2580:
2552:
2549:
2548:
2506:
2492:
2490:
2488:
2485:
2484:
2468:
2465:
2464:
2436:
2433:
2432:
2404:
2401:
2400:
2372:
2369:
2368:
2343:
2340:
2339:
2323:
2320:
2319:
2303:
2300:
2299:
2283:
2280:
2279:
2251:
2248:
2247:
2222:
2219:
2218:
2193:
2190:
2189:
2161:
2158:
2157:
2129:
2126:
2125:
2080:
2075:
2073:
2070:
2069:
2041:
2038:
2037:
2021:
2018:
2017:
2001:
1998:
1997:
1955:
1950:
1948:
1945:
1944:
1928:
1925:
1924:
1903:
1901:
1898:
1897:
1876:
1874:
1871:
1870:
1854:
1851:
1850:
1834:
1831:
1830:
1814:
1811:
1810:
1794:
1791:
1790:
1750:
1747:
1746:
1706:
1703:
1702:
1674:
1671:
1670:
1654:
1651:
1650:
1634:
1631:
1630:
1614:
1611:
1610:
1594:
1591:
1590:
1562:
1559:
1558:
1530:
1527:
1526:
1498:
1495:
1494:
1478:
1470:
1468:
1465:
1464:
1436:
1433:
1432:
1404:
1401:
1400:
1372:
1369:
1368:
1326:
1321:
1319:
1316:
1315:
1299:
1296:
1295:
1253:
1219:
1215:
1213:
1210:
1209:
1168:
1165:
1164:
1123:
1120:
1119:
1018:
1014:
1010:
1008:
1007:
977:
972:
921:Interval graphs
864:
860:
856:
852:
838:
821:
817:
804:
800:
792:
784:
781:
780:
762:triangle graphs
739:
725:interval graphs
704:
651:
647:
645:
642:
641:
584:
563:
560:
559:
543:
540:
539:
521:
518:
517:
501:
498:
497:
477:
474:
473:
448:
445:
444:
407:
404:
403:
380:
377:
376:
351:
348:
347:
327:
324:
323:
321:independent set
286:
283:
282:
279:
247:
241:
213:independent set
202:
196:
167:
155:
143:
135:
123:
115:
110:
109:
104:
103:
99:
95:
91:
84:
78:
64:independent set
32:
17:
12:
11:
5:
5834:
5824:
5823:
5818:
5803:
5802:
5781:
5726:
5716:(3): 505–517,
5705:
5680:
5653:(2): 173–186,
5642:
5597:
5583:
5562:
5544:
5527:10.1.1.138.705
5513:
5500:
5479:
5458:
5440:(3): 558–565,
5423:Lenstra, J. K.
5415:
5391:
5381:(3): 119–123,
5367:Yannakakis, M.
5363:Johnson, D. S.
5359:
5350:
5340:(4): 463–470,
5326:
5305:
5277:(4): 233–234,
5261:
5223:
5193:(2): 131–140,
5170:
5156:
5138:(1): 210–223,
5123:
5117:
5098:
5093:10.1.1.48.4074
5079:
5047:
5045:
5042:
5040:
5039:
5024:
5006:
4989:
4982:
4956:
4945:(4): 567–583.
4926:
4911:
4890:
4869:(6): 400–408.
4849:
4830:(3): 163–174.
4810:
4791:(4): 777–788.
4771:
4755:
4703:
4683:
4667:
4646:
4611:
4574:
4534:
4514:
4494:
4474:
4443:
4431:
4416:
4414:
4411:
4408:
4407:
4361:
4360:
4358:
4355:
4342:
4339:
4336:
4333:
4312:
4309:
4306:
4303:
4300:
4297:
4284:
4281:
4266:
4262:
4258:
4238:
4233:
4229:
4225:
4222:
4202:
4199:
4196:
4193:
4171:
4167:
4163:
4143:
4123:
4118:
4114:
4110:
4107:
4104:
4095:runtime using
4084:
4081:
4078:
4073:
4069:
4065:
4062:
4040:
4036:
4032:
4012:
4007:
4003:
3999:
3996:
3976:
3973:
3970:
3965:
3961:
3957:
3954:
3934:
3914:
3909:
3905:
3901:
3898:
3895:
3891:
3887:
3884:
3881:
3878:
3858:
3855:
3852:
3847:
3843:
3839:
3836:
3814:
3810:
3806:
3790:
3787:
3752:
3748:
3744:
3714:
3710:
3706:
3686:
3683:
3681:
3678:
3650:
3647:
3611:
3608:
3607:
3606:
3594:
3591:
3588:
3585:
3582:
3577:
3573:
3569:
3566:
3563:
3560:
3557:
3554:
3551:
3548:
3545:
3542:
3539:
3536:
3533:
3530:
3527:
3524:
3504:
3500:
3495:
3492:
3489:
3485:
3482:
3477:
3473:
3469:
3466:
3455:
3443:
3440:
3437:
3434:
3431:
3428:
3425:
3422:
3402:
3399:
3396:
3393:
3390:
3387:
3384:
3381:
3353:
3349:
3344:
3341:
3338:
3334:
3331:
3328:
3325:
3322:
3307:
3281:
3277:
3272:
3268:
3236:
3232:
3227:
3224:
3221:
3217:
3214:
3209:
3205:
3201:
3198:
3170:
3167:
3164:
3161:
3158:
3153:
3149:
3145:
3142:
3122:
3119:
3116:
3113:
3110:
3105:
3101:
3097:
3094:
3073:
3072:
3069:
3068:
3067:
3064:
3061:
3058:
3051:
3045:
3037:
3036:
3033:
3032:
3031:
3028:
3025:
3019:
2995:
2992:
2991:
2990:
2978:
2975:
2972:
2969:
2966:
2963:
2960:
2957:
2937:
2934:
2931:
2928:
2925:
2922:
2917:
2913:
2909:
2905:
2901:
2890:
2876:
2871:
2867:
2863:
2838:
2834:
2830:
2808:
2804:
2800:
2796:
2793:
2788:
2785:
2781:
2778:
2775:
2770:
2749:
2746:
2740:
2737:
2734:
2731:
2728:
2725:
2722:
2719:
2716:
2711:
2708:
2705:
2702:
2699:
2696:
2693:
2690:
2687:
2664:
2661:
2658:
2655:
2652:
2629:
2626:
2623:
2620:
2617:
2614:
2611:
2608:
2605:
2600:
2597:
2594:
2591:
2568:
2565:
2562:
2559:
2556:
2533:
2530:
2527:
2524:
2521:
2518:
2515:
2512:
2509:
2504:
2501:
2498:
2495:
2472:
2452:
2449:
2446:
2443:
2440:
2429:
2417:
2414:
2411:
2408:
2388:
2385:
2382:
2379:
2376:
2356:
2353:
2350:
2347:
2327:
2307:
2287:
2267:
2264:
2261:
2258:
2255:
2235:
2232:
2229:
2226:
2206:
2203:
2200:
2197:
2177:
2174:
2171:
2168:
2165:
2145:
2142:
2139:
2136:
2133:
2122:
2107:
2104:
2101:
2098:
2095:
2092:
2089:
2086:
2083:
2079:
2057:
2054:
2051:
2048:
2045:
2025:
2005:
1982:
1979:
1976:
1973:
1970:
1967:
1964:
1961:
1958:
1954:
1932:
1910:
1907:
1883:
1880:
1858:
1838:
1818:
1798:
1778:
1775:
1772:
1769:
1766:
1763:
1760:
1757:
1754:
1734:
1731:
1728:
1725:
1722:
1719:
1716:
1713:
1710:
1690:
1687:
1684:
1681:
1678:
1658:
1638:
1618:
1598:
1578:
1575:
1572:
1569:
1566:
1546:
1543:
1540:
1537:
1534:
1514:
1511:
1508:
1505:
1502:
1481:
1477:
1473:
1463:. Notice that
1452:
1449:
1446:
1443:
1440:
1431:and the other
1420:
1417:
1414:
1411:
1408:
1388:
1385:
1382:
1379:
1376:
1353:
1350:
1347:
1344:
1341:
1338:
1335:
1332:
1329:
1325:
1303:
1278:
1277:
1274:
1273:
1272:
1269:
1266:
1260:
1252:
1249:
1236:
1233:
1230:
1227:
1222:
1218:
1193:
1190:
1187:
1184:
1181:
1178:
1175:
1172:
1161:
1160:
1148:
1145:
1142:
1139:
1136:
1133:
1130:
1127:
1108:
1105:
1102:
1098:
1094:
1085:
1067:Call a node v
1051:
1050:
1047:
1046:
1045:
1042:
1039:
1035:
1029:
1006:
1003:
1002:
1001:
998:
997:
996:
993:
990:
984:
976:
973:
971:
968:
948:Perrin numbers
925:chordal graphs
886:
885:
874:
867:
863:
859:
855:
851:
848:
845:
841:
837:
834:
829:
824:
820:
816:
813:
810:
807:
803:
799:
795:
791:
788:
738:
735:
703:
700:
696:dominating set
654:
650:
592:maximal clique
583:
580:
567:
547:
525:
505:
493:
492:
481:
461:
458:
455:
452:
432:
429:
426:
423:
420:
417:
414:
411:
401:
390:
387:
384:
361:
358:
355:
331:
308:
305:
302:
299:
296:
293:
290:
278:
275:
245:
200:
182:dominating set
82:
66:that is not a
15:
9:
6:
4:
3:
2:
5833:
5822:
5819:
5817:
5814:
5813:
5811:
5799:
5795:
5791:
5787:
5782:
5778:
5774:
5770:
5766:
5762:
5758:
5754:
5750:
5745:
5740:
5737:(5): 056127,
5736:
5732:
5727:
5723:
5719:
5715:
5711:
5706:
5701:
5696:
5692:
5688:
5687:
5681:
5678:
5674:
5670:
5666:
5661:
5656:
5652:
5648:
5643:
5639:
5635:
5631:
5627:
5622:
5617:
5613:
5609:
5608:
5603:
5600:Moon, J. W.;
5598:
5594:
5590:
5586:
5580:
5576:
5572:
5568:
5563:
5560:
5559:9783540278108
5556:
5555:9783540223399
5552:
5547:
5541:
5537:
5533:
5528:
5523:
5519:
5514:
5511:
5507:
5503:
5501:0-8186-2136-2
5497:
5493:
5489:
5485:
5480:
5476:
5472:
5468:
5464:
5459:
5455:
5451:
5447:
5443:
5439:
5435:
5428:
5424:
5420:
5419:Lawler, E. L.
5416:
5412:
5408:
5404:
5400:
5396:
5395:Lawler, E. L.
5392:
5388:
5384:
5380:
5376:
5372:
5368:
5364:
5360:
5356:
5351:
5347:
5343:
5339:
5335:
5331:
5327:
5323:
5319:
5316:(2): 05.2.6,
5315:
5311:
5306:
5302:
5298:
5294:
5290:
5285:
5280:
5276:
5272:
5271:
5266:
5262:
5258:
5254:
5250:
5246:
5241:
5240:cs.DS/0407036
5236:
5232:
5228:
5224:
5220:
5216:
5211:
5206:
5201:
5200:cs.DS/0011009
5196:
5192:
5188:
5187:
5179:
5175:
5171:
5166:
5162:
5157:
5153:
5149:
5145:
5141:
5137:
5133:
5129:
5128:Nishizeki, T.
5124:
5120:
5118:9780898715385
5114:
5110:
5109:
5104:
5099:
5094:
5089:
5085:
5080:
5075:
5070:
5066:
5062:
5058:
5057:-cycle graph"
5056:
5049:
5048:
5035:
5028:
5017:
5010:
5002:
5001:
4993:
4985:
4979:
4975:
4971:
4967:
4960:
4952:
4948:
4944:
4940:
4933:
4931:
4922:
4915:
4904:
4897:
4895:
4886:
4882:
4877:
4872:
4868:
4864:
4860:
4853:
4845:
4841:
4837:
4833:
4829:
4825:
4821:
4814:
4806:
4802:
4798:
4794:
4790:
4786:
4782:
4775:
4768:
4764:
4759:
4752:
4748:
4744:
4740:
4736:
4732:
4728:
4724:
4720:
4716:
4712:
4707:
4700:
4696:
4692:
4687:
4680:
4679:Byskov (2003)
4676:
4671:
4662:
4657:
4650:
4642:
4638:
4634:
4630:
4626:
4622:
4615:
4596:
4589:
4583:
4581:
4579:
4570:
4566:
4561:
4556:
4552:
4548:
4541:
4539:
4531:
4530:Füredi (1987)
4527:
4523:
4518:
4511:
4507:
4503:
4498:
4491:
4487:
4483:
4482:Byskov (2003)
4478:
4471:
4467:
4464:
4460:
4456:
4453:
4447:
4440:
4435:
4429:
4424:
4422:
4417:
4403:
4399:
4392:
4388:
4384:
4380:
4371:
4366:
4362:
4354:
4337:
4331:
4307:
4304:
4301:
4295:
4280:
4264:
4260:
4256:
4231:
4227:
4220:
4197:
4191:
4169:
4165:
4161:
4141:
4116:
4112:
4108:
4102:
4079:
4076:
4071:
4067:
4060:
4038:
4034:
4030:
4005:
4001:
3994:
3971:
3968:
3963:
3959:
3952:
3932:
3907:
3899:
3896:
3893:
3889:
3885:
3876:
3853:
3850:
3845:
3841:
3834:
3812:
3808:
3804:
3796:
3786:
3784:
3780:
3776:
3771:
3768:
3750:
3746:
3742:
3734:
3730:
3712:
3708:
3704:
3696:
3692:
3677:
3675:
3670:
3668:
3664:
3660:
3656:
3646:
3644:
3638:
3636:
3632:
3628:
3627:Lawler (1976)
3624:
3617:
3586:
3580:
3575:
3571:
3564:
3561:
3552:
3546:
3543:
3537:
3531:
3528:
3522:
3502:
3498:
3490:
3483:
3480:
3475:
3471:
3467:
3464:
3456:
3435:
3429:
3426:
3420:
3394:
3388:
3385:
3379:
3371:
3367:
3351:
3347:
3339:
3332:
3329:
3326:
3323:
3320:
3312:
3308:
3305:
3301:
3297:
3279:
3275:
3270:
3266:
3258:
3254:
3250:
3234:
3230:
3222:
3215:
3212:
3207:
3203:
3199:
3196:
3188:
3184:
3183:
3182:
3162:
3156:
3151:
3147:
3140:
3114:
3108:
3103:
3099:
3092:
3084:
3080:
3078:
3070:
3065:
3062:
3059:
3056:
3052:
3049:
3048:
3046:
3043:
3042:
3041:
3034:
3029:
3026:
3023:
3022:
3020:
3017:
3016:
3015:
3013:
3002:
2970:
2964:
2961:
2955:
2935:
2932:
2926:
2920:
2915:
2911:
2907:
2903:
2899:
2891:
2874:
2865:
2832:
2802:
2794:
2791:
2786:
2783:
2779:
2776:
2773:
2768:
2747:
2744:
2735:
2729:
2726:
2720:
2714:
2706:
2700:
2697:
2691:
2685:
2659:
2656:
2653:
2624:
2618:
2615:
2609:
2603:
2595:
2589:
2563:
2557:
2528:
2522:
2519:
2513:
2507:
2499:
2493:
2470:
2447:
2441:
2430:
2412:
2406:
2383:
2377:
2351:
2345:
2325:
2305:
2285:
2262:
2256:
2230:
2224:
2201:
2195:
2172:
2166:
2140:
2134:
2123:
2102:
2096:
2093:
2087:
2081:
2077:
2052:
2046:
2023:
2003:
1977:
1971:
1968:
1962:
1956:
1952:
1930:
1908:
1905:
1881:
1878:
1856:
1836:
1816:
1796:
1773:
1767:
1764:
1758:
1752:
1729:
1723:
1720:
1714:
1708:
1685:
1679:
1656:
1636:
1616:
1596:
1573:
1567:
1541:
1535:
1509:
1506:
1503:
1475:
1447:
1444:
1441:
1415:
1412:
1409:
1383:
1380:
1377:
1348:
1342:
1339:
1333:
1327:
1323:
1301:
1293:
1292:
1291:
1289:
1285:
1283:
1275:
1270:
1267:
1264:
1263:
1261:
1258:
1257:
1256:
1248:
1231:
1225:
1220:
1216:
1207:
1185:
1179:
1176:
1140:
1134:
1131:
1125:
1117:
1113:
1109:
1106:
1103:
1099:
1095:
1091:
1086:
1082:
1081:
1080:
1078:
1074:
1070:
1065:
1063:
1059:
1055:
1048:
1043:
1040:
1036:
1033:
1032:
1030:
1027:
1026:
1025:
1023:
1013:
999:
994:
991:
988:
987:
985:
982:
981:
980:
967:
965:
964:plastic ratio
961:
957:
953:
949:
945:
941:
936:
934:
933:sparse graphs
930:
926:
922:
918:
914:
910:
906:
905:planar graphs
902:
898:
894:
889:
872:
865:
857:
849:
846:
843:
839:
835:
822:
814:
808:
805:
797:
793:
789:
779:
778:
777:
775:
771:
767:
763:
759:
755:
751:
747:
743:
734:
732:
728:
726:
722:
718:
714:
710:
699:
697:
692:
690:
686:
682:
678:
674:
652:
648:
638:
634:
631:
629:
625:
621:
617:
613:
609:
605:
601:
597:
593:
589:
579:
565:
558:cannot be in
545:
536:
523:
503:
479:
456:
450:
427:
424:
421:
415:
409:
402:
388:
385:
382:
375:
374:
373:
359:
356:
353:
345:
329:
322:
303:
300:
297:
291:
288:
274:
272:
270:
264:
262:
256:
244:
240:
235:
231:
229:
225:
224:vector spaces
220:
218:
214:
212:
199:
193:
189:
187:
183:
178:
175:
171:
163:
159:
151:
147:
139:
131:
127:
119:
89:
81:
75:
73:
69:
65:
61:
57:
53:
49:
41:
36:
30:
26:
22:
5792:(1–2): 1–8,
5789:
5785:
5734:
5731:Phys. Rev. E
5730:
5713:
5709:
5693:(1): 28–42,
5690:
5684:
5650:
5646:
5611:
5605:
5566:
5517:
5483:
5466:
5462:
5437:
5433:
5405:(3): 66–67,
5402:
5398:
5378:
5374:
5354:
5337:
5333:
5313:
5309:
5274:
5268:
5230:
5227:Eppstein, D.
5190:
5184:
5174:Eppstein, D.
5160:
5135:
5131:
5107:
5102:
5083:
5064:
5060:
5054:
5033:
5027:
5009:
4998:
4992:
4965:
4959:
4942:
4938:
4920:
4914:
4866:
4862:
4852:
4827:
4823:
4813:
4788:
4784:
4774:
4758:
4706:
4686:
4670:
4649:
4627:(5–6): 331.
4624:
4620:
4614:
4602:. Retrieved
4595:the original
4550:
4546:
4526:Euler (2005)
4517:
4505:
4497:
4477:
4446:
4434:
4401:
4397:
4390:
4382:
4378:
4370:Erdős (1966)
4365:
4286:
3792:
3772:
3688:
3671:
3652:
3639:
3619:
3365:
3310:
3303:
3299:
3295:
3256:
3248:
3189:, we select
3186:
3185:If, in step
3082:
3081:
3076:
3075:Setting δ=1/
3074:
3054:
3038:
3008:
1849:is neighbor
1701:occurs when
1287:
1286:
1281:
1279:
1254:
1205:
1162:
1115:
1111:
1093:1-exp(-1/6).
1089:
1076:
1072:
1068:
1066:
1061:
1057:
1053:
1052:
1021:
1019:
978:
951:
944:cycle graphs
939:
937:
928:
916:
912:
908:
900:
896:
892:
890:
887:
773:
769:
757:
753:
745:
740:
729:
712:
708:
705:
693:
681:vertex cover
676:
670:
632:
623:
619:
615:
611:
595:
591:
587:
585:
537:
494:
343:
281:For a graph
280:
268:
260:
252:
242:
221:
210:
207:
197:
195:The top two
185:
179:
173:
169:
161:
157:
149:
145:
137:
129:
125:
117:
79:
76:
59:
55:
51:
48:graph theory
45:
5126:Chiba, N.;
4863:Commun. ACM
4743:Stix (2004)
4604:21 February
3691:parallelize
3063:Add W to I;
3027:Add W to I;
2338:removed is
956:path graphs
766:Turán graph
114:, the sets
5810:Categories
5330:Füredi, Z.
5067:: 08.5.7,
5044:References
4510:arboricity
3775:PRAM model
3695:P-Complete
3631:complement
673:complement
277:Definition
259:finding a
239:star graph
5655:CiteSeerX
5614:: 23–28,
5602:Moser, L.
5522:CiteSeerX
5510:122685841
5469:: 22–35,
5301:121993028
5265:Erdős, P.
5205:CiteSeerX
5152:207051803
5088:CiteSeerX
4844:0166-218X
4805:0097-5397
4661:1202.3205
4555:CiteSeerX
4389:(log log
4357:Footnotes
4305:
4077:
3969:
3897:
3851:
3635:bipartite
3581:
3547:
3532:
3484:
3465:δ
3430:
3389:
3333:
3321:δ
3216:
3197:δ
3157:
3109:
3071:Return I.
3035:Return I.
2965:
2948:which is
2921:
2784:∈
2769:∑
2561:→
2445:→
2381:→
2260:→
2170:→
2138:→
2050:→
1683:→
1571:→
1539:→
1276:Return I.
1226:
1180:
1171:Θ
1135:
1114:), where
1101:constant.
1049:Return I.
1000:Return I.
854:⌋
833:⌊
809:−
802:⌋
787:⌊
431:∅
428:≠
422:∩
386:∈
357:∈
5777:16773685
5769:11414981
5677:17824282
5454:29527771
5176:(2003),
4885:14323396
4641:36720853
4466:Archived
4455:Archived
4053:with an
3925:, where
3674:cographs
3368:), then
3247:, where
3083:ANALYSIS
2399:removes
1789:, where
1288:ANALYSIS
1054:ANALYSIS
954:-vertex
942:-vertex
907:: every
731:Cographs
267:listing
228:matroids
5749:Bibcode
5638:9855414
5630:0182577
5593:5254186
5318:Bibcode
5293:0205874
5257:2769046
3797:zoo of
3731:or the
3685:History
2278:, when
1294:A node
772:in any
604:induces
598:in the
346:if for
211:maximum
5775:
5767:
5675:
5657:
5636:
5628:
5591:
5581:
5553:
5542:
5524:
5508:
5498:
5452:
5299:
5291:
5255:
5207:
5150:
5115:
5090:
4980:
4883:
4842:
4803:
4697:, see
4639:
4557:
4400:– log
4381:– log
3987:using
3869:using
2998:": -->
1038:names.
1009:": -->
723:, and
443:where
261:single
98:, and
72:vertex
68:subset
62:is an
5773:S2CID
5739:arXiv
5673:S2CID
5634:S2CID
5589:S2CID
5506:S2CID
5450:S2CID
5430:(PDF)
5297:S2CID
5253:S2CID
5235:arXiv
5195:arXiv
5181:(PDF)
5148:S2CID
5069:arXiv
5019:(PDF)
4906:(PDF)
4881:S2CID
4656:arXiv
4637:S2CID
4598:(PDF)
4591:(PDF)
4413:Notes
342:is a
319:, an
58:) or
5765:PMID
5579:ISBN
5551:ISBN
5540:ISBN
5496:ISBN
5113:ISBN
4978:ISBN
4840:ISSN
4801:ISSN
4606:2015
4488:and
4461:and
3653:The
3302:<
3000:edit
2217:and
2156:and
1829:and
1765:<
1745:and
1721:<
1629:and
1557:and
1077:good
1011:edit
923:and
671:The
265:and
253:Two
226:and
188:.
166:and
122:and
108:and
88:path
86:, a
50:, a
38:The
5794:doi
5757:doi
5718:doi
5695:doi
5691:363
5665:doi
5616:doi
5571:doi
5532:doi
5488:doi
5471:doi
5442:doi
5407:doi
5383:doi
5342:doi
5279:doi
5245:doi
5215:doi
5140:doi
4970:doi
4947:doi
4871:doi
4832:doi
4793:doi
4629:doi
4565:doi
4302:log
4068:log
3960:log
3894:log
3842:log
3781:on
3572:log
3544:log
3529:log
3481:log
3427:log
3386:log
3370:WHP
3330:log
3253:WHP
3213:log
3148:log
3100:log
2962:log
2904:log
1290::
1217:log
1177:log
1132:log
1073:bad
1069:bad
1024:).
862:mod
819:mod
760:/3
594:or
586:If
269:all
56:MIS
46:In
5812::
5790:47
5788:,
5771:,
5763:,
5755:,
5747:,
5735:63
5733:,
5712:,
5689:,
5671:,
5663:,
5651:27
5649:,
5632:,
5626:MR
5624:,
5610:,
5587:,
5577:,
5557:,
5549:.
5538:,
5530:,
5504:,
5494:,
5465:,
5448:,
5436:,
5432:,
5421:;
5401:,
5379:27
5377:,
5369:;
5365:;
5338:11
5336:,
5312:,
5295:,
5289:MR
5287:,
5273:,
5251:,
5243:,
5213:,
5203:,
5189:,
5183:,
5163:,
5146:,
5136:14
5134:,
5065:11
5063:,
5059:,
4976:.
4968:.
4941:.
4929:^
4893:^
4879:.
4867:26
4865:.
4861:.
4838:.
4826:.
4822:.
4799:.
4789:12
4787:.
4783:.
4765:;
4749:;
4745:;
4741:;
4737:;
4733:;
4729:;
4725:;
4721:;
4717:;
4713:;
4677:;
4635:.
4625:23
4623:.
4577:^
4563:.
4551:15
4549:.
4537:^
4528:;
4524:;
4420:^
4385:–
4279:.
3676:.
3669:.
3663:#P
1589:,
1247:.
1079:.
966:.
935:.
727:.
719:,
630:.
606:a
273:.
230:.
219:.
176:}.
172:,
164:}
160:,
152:}.
148:,
140:}
132:}
128:,
120:}
111:bc
105:ab
94:,
5801:.
5796::
5780:.
5759::
5751::
5741::
5725:.
5720::
5714:6
5704:.
5697::
5667::
5641:.
5618::
5612:3
5596:.
5573::
5561:.
5534::
5490::
5478:.
5473::
5467:5
5457:.
5444::
5438:9
5414:.
5409::
5403:5
5390:.
5385::
5349:.
5344::
5325:.
5320::
5314:8
5304:.
5281::
5275:4
5260:.
5247::
5237::
5222:.
5217::
5197::
5191:7
5169:.
5155:.
5142::
5122:.
5103:k
5097:.
5078:.
5071::
5055:n
5036:.
5021:.
5003:.
4986:.
4972::
4953:.
4949::
4943:7
4923:.
4908:.
4887:.
4873::
4846:.
4834::
4828:3
4807:.
4795::
4769:.
4753:.
4701:.
4681:.
4664:.
4658::
4643:.
4631::
4608:.
4571:.
4567::
4532:.
4506:n
4492:.
4472:.
4441:.
4405:.
4402:n
4398:n
4393:)
4391:n
4387:O
4383:n
4379:n
4374:n
4341:)
4338:1
4335:(
4332:O
4311:)
4308:n
4299:(
4296:O
4265:1
4261:C
4257:N
4237:)
4232:2
4228:n
4224:(
4221:O
4201:)
4198:m
4195:(
4192:O
4170:2
4166:C
4162:N
4142:m
4122:)
4117:2
4113:n
4109:m
4106:(
4103:O
4083:)
4080:n
4072:2
4064:(
4061:O
4039:2
4035:C
4031:N
4011:)
4006:2
4002:n
3998:(
3995:O
3975:)
3972:n
3964:4
3956:(
3953:O
3933:n
3913:)
3908:3
3904:)
3900:n
3890:/
3886:n
3883:(
3880:(
3877:O
3857:)
3854:n
3846:4
3838:(
3835:O
3813:4
3809:C
3805:N
3751:2
3747:C
3743:N
3713:1
3709:C
3705:N
3605:.
3593:)
3590:)
3587:n
3584:(
3576:2
3568:(
3565:O
3562:=
3559:)
3556:)
3553:n
3550:(
3541:)
3538:D
3535:(
3526:(
3523:O
3503:D
3499:/
3494:)
3491:n
3488:(
3476:i
3472:2
3468:=
3442:)
3439:)
3436:n
3433:(
3424:(
3421:O
3401:)
3398:)
3395:n
3392:(
3383:(
3380:O
3366:C
3352:d
3348:/
3343:)
3340:n
3337:(
3327:C
3324:=
3311:d
3304:n
3300:D
3296:D
3280:i
3276:2
3271:/
3267:D
3257:i
3249:D
3235:D
3231:/
3226:)
3223:n
3220:(
3208:i
3204:2
3200:=
3187:i
3169:)
3166:)
3163:n
3160:(
3152:2
3144:(
3141:O
3121:)
3118:)
3115:n
3112:(
3104:2
3096:(
3093:O
3077:n
3055:n
3004:]
2989:.
2977:)
2974:)
2971:n
2968:(
2959:(
2956:O
2936:1
2933:+
2930:)
2927:m
2924:(
2916:3
2912:/
2908:4
2900:3
2875:2
2870:|
2866:E
2862:|
2837:|
2833:E
2829:|
2807:|
2803:E
2799:|
2795:=
2792:1
2787:E
2780:w
2777:,
2774:v
2748:1
2745:=
2739:)
2736:v
2733:(
2730:d
2727:+
2724:)
2721:w
2718:(
2715:d
2710:)
2707:v
2704:(
2701:d
2698:+
2695:)
2692:w
2689:(
2686:d
2663:)
2660:v
2657:,
2654:w
2651:(
2628:)
2625:v
2622:(
2619:d
2616:+
2613:)
2610:w
2607:(
2604:d
2599:)
2596:v
2593:(
2590:d
2567:)
2564:v
2558:w
2555:(
2532:)
2529:w
2526:(
2523:d
2520:+
2517:)
2514:v
2511:(
2508:d
2503:)
2500:w
2497:(
2494:d
2471:w
2451:)
2448:w
2442:v
2439:(
2416:)
2413:v
2410:(
2407:d
2387:)
2384:v
2378:w
2375:(
2355:)
2352:w
2349:(
2346:d
2326:w
2306:w
2286:v
2266:)
2263:w
2257:v
2254:(
2234:)
2231:v
2228:(
2225:d
2205:)
2202:w
2199:(
2196:d
2176:)
2173:v
2167:w
2164:(
2144:)
2141:w
2135:v
2132:(
2106:)
2103:v
2100:(
2097:d
2094:+
2091:)
2088:w
2085:(
2082:d
2078:1
2056:)
2053:v
2047:w
2044:(
2024:w
2004:v
1981:)
1978:w
1975:(
1972:d
1969:+
1966:)
1963:v
1960:(
1957:d
1953:1
1931:v
1909:3
1906:1
1882:2
1879:1
1857:w
1837:x
1817:v
1797:w
1777:)
1774:x
1771:(
1768:r
1762:)
1759:v
1756:(
1753:r
1733:)
1730:w
1727:(
1724:r
1718:)
1715:v
1712:(
1709:r
1689:)
1686:w
1680:v
1677:(
1657:v
1637:w
1617:w
1597:v
1577:)
1574:v
1568:w
1565:(
1545:)
1542:w
1536:v
1533:(
1513:)
1510:w
1507:,
1504:v
1501:(
1480:|
1476:E
1472:|
1451:)
1448:v
1445:,
1442:w
1439:(
1419:)
1416:w
1413:,
1410:v
1407:(
1387:)
1384:w
1381:,
1378:v
1375:(
1352:)
1349:w
1346:(
1343:d
1340:+
1337:)
1334:v
1331:(
1328:d
1324:1
1302:v
1282:n
1235:)
1232:n
1229:(
1221:4
1206:n
1192:)
1189:)
1186:n
1183:(
1174:(
1159:.
1147:)
1144:)
1141:n
1138:(
1129:(
1126:O
1116:m
1112:m
1022:n
1015:]
952:n
940:n
929:n
917:n
913:n
909:n
901:n
897:n
893:n
873:.
866:k
858:n
850:1
847:+
844:k
840:/
836:n
828:)
823:k
815:n
812:(
806:k
798:k
794:/
790:n
774:n
770:k
758:n
754:n
750:3
746:n
653:3
649:K
624:S
620:S
616:S
612:S
588:S
566:S
546:S
524:S
504:S
480:v
460:)
457:v
454:(
451:N
425:S
419:)
416:v
413:(
410:N
389:S
383:v
360:V
354:v
330:S
307:)
304:E
301:,
298:V
295:(
292:=
289:G
246:8
243:S
201:3
198:P
174:c
170:b
168:{
162:b
158:a
156:{
150:c
146:a
144:{
138:a
136:{
130:c
126:a
124:{
118:b
116:{
100:c
96:b
92:a
83:3
80:P
54:(
31:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
