{"entities":{"Q750320":{"pageid":752169,"ns":120,"title":"Item:Q750320","lastrevid":49435693,"modified":"2026-01-07T03:54:41Z","type":"item","id":"Q750320","labels":{"en":{"language":"en","value":"TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4174697"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750320$0E61B84E-CDB4-47AE-9175-E1049451AECD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cb76612daec1af201d124f663da7f98efc57cbfe","datavalue":{"value":{"text":"TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q750320$00AD6785-3727-4D18-A6DE-2D3A5D65ECED","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e9dc918c8542d632ec89ceb306bd68cc11aad093","datavalue":{"value":"0713.90087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750320$4C1F7CCF-8ADD-4FB2-9BFF-E98A16D908FD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0693ca7417cb3a60f81e5a0b0896656ff62e960b","datavalue":{"value":"10.1016/0305-0548(90)90048-C","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750320$C99AB4FD-7C7D-4AD3-8AE6-968617C64576","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c1706c07a64f697fbeb23788bde797594be484f0","datavalue":{"value":{"entity-type":"item","numeric-id":750319,"id":"Q750319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750320$1B610107-9A01-4D92-AFCE-F742EC08B31F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4249c9a7a0b14df0599e70315ca2a040457d857c","datavalue":{"value":{"entity-type":"item","numeric-id":260023,"id":"Q260023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750320$B9B2595D-C09D-4704-AC06-2DBFCBBE05AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"467bce3dcf8136ea7a4832a7c85d350a56e9a245","datavalue":{"value":{"entity-type":"item","numeric-id":224825,"id":"Q224825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750320$74D4E2BF-0597-4D59-94C2-58EC588CFE21","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e630590c5ca6e787c3c7b5e291898405495fea2b","datavalue":{"value":{"entity-type":"item","numeric-id":162215,"id":"Q162215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750320$90134B66-0C96-4AC5-9330-4606127E7BDF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q750320$4735196C-D4B1-4E1E-96EC-3342D20E1C87","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b3d26e0513c17fbb2355892ffa60115a7946b214","datavalue":{"value":"In an arbitrary graph G a subset S of nodes is independent if no two nodes of S are linked by an edge of G; and S is independent in G if and only if it is a clique in the complement \\(\\bar G\\) of G. This gives rise to the difficult problem to find in G an independent set with maximum cardinality. Already several exact procedures for graphs of moderate size are known, especially the Balas-Yu algorithm.    In the present paper a further algorithm is developed which is an exact implicit enumeration procedure, which uses bounds on the independence number of a subgraph and which is also applicable to graphs of larger size. To find such bounds Tabu Search (TS) techniques are used, and the general method of TS is described in Table 2. The new algorithm is called TABARIS (Tabu And Branch and Bound Applied Repeatedly for Independent Sets); its general procedure is described in detail in a formalized manner (Table 1) and among other things it contains the solution of the following two problems which imply the above mentioned specializations of TS: (1) Finding a large stable set; (2) covering a large node set with certain cliques.    These steps and their algorithms are again stated in a formalized manner by tables and the solution of (1) is accomplished by a heuristic procedure which is called STABULARGE (Table 3). To solve (2) three sequential algorithms are given, which are formulated in Tables 4 and 5. - Computational experiments have been performed on random graphs with 40- 400 nodes and with densities between 0.1 and 0.9; the obtained results by applying TABARIS and the Balas-Yu algorithm both are compared and analyzed (Table 6). Finally TABARIS was applied to random graphs with 450 nodes (density 0.5), to one graph with 500 nodes (density 0.5) and to one graph with 1000 nodes (density 0.7) and the results reported in Table 7.","type":"string"},"datatype":"string"},"type":"statement","id":"Q750320$48E43574-9CC7-4A81-B5D3-C419B758E55C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750320$127688AB-D751-4319-B48C-E50A9A524599","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d550400b67148ac150a943881fbd05e682ea56f5","datavalue":{"value":"90-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750320$804CEBF3-C679-4D71-B669-9B191FCBF90F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750320$F6FC285D-7281-46CF-B3C4-5662BA9A75C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750320$7A0B2C62-DF17-4CDD-9BDD-4B40E5288451","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e038e5e16128fe63d90643b4c4804d63f3db1339","datavalue":{"value":"90C06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750320$489B2151-A082-4A98-A564-A26396F99FF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750320$5817D478-55ED-44B1-AE14-B806356172F6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"10a0729b7b88a39574e2abe87b5e706d4c7c7df3","datavalue":{"value":"4174697","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750320$5B40BEC7-BC61-451A-984E-18126FCF25C6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93b82e32a5e019add222df424aa14ad2c7f7afa1","datavalue":{"value":"maximum independent set in a graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q750320$65A14453-4E23-498A-908D-D4563208C745","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"97d4b4178c14eed3b6a7898ab89a861c935edc2c","datavalue":{"value":"computational comparison of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q750320$2FA05329-97C2-4F47-B6BE-E0704B7A3089","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f1609aeb3e17d2c968997d45010add4857cb499","datavalue":{"value":"Balas-Yu algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q750320$13A37D3A-9ED0-449D-BCDF-4E3C4C00747F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff8bef9d2781a0bc06aa53226b28c1b5199f3150","datavalue":{"value":"exact implicit enumeration","type":"string"},"datatype":"string"},"type":"statement","id":"Q750320$18752C1A-404A-4DA9-918B-2320F6A81BFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ccfc39c23685e2a3a186c1f1985ab1522e91ce0a","datavalue":{"value":"Tabu Search","type":"string"},"datatype":"string"},"type":"statement","id":"Q750320$15B85F02-6CF2-408D-8266-BBFCB592A404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"763d7a092420e14db81235866ba36fe04a9c7aa3","datavalue":{"value":"TABARIS","type":"string"},"datatype":"string"},"type":"statement","id":"Q750320$DC0ECB72-EB54-4590-BA26-B6ADFC46A109","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f641bd239fe6f0d5fb2cc0d2b3f89cbc609bab87","datavalue":{"value":"heuristic","type":"string"},"datatype":"string"},"type":"statement","id":"Q750320$C3F3AE4C-E5DB-4E23-A806-C906D4CBF129","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"54eadc8258ca0a21ba3eb6b49d67a27ba79d9763","datavalue":{"value":"STABULARGE","type":"string"},"datatype":"string"},"type":"statement","id":"Q750320$7F6A3513-9781-4B6E-BB57-0134FA5796D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4f51776dadcb1bfead92cdaa8c678dc729e342b","datavalue":{"value":"random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q750320$0B7A3269-5A22-41D7-9651-8EFE4712631F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"31cef456e8646accdc28b523a232a52220366047","datavalue":{"value":{"entity-type":"item","numeric-id":593309,"id":"Q593309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750320$2430B462-FED5-45FB-BA86-3AD1591F5B04","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"0bd02c26dee295e17fa1661a740b0e3277993f7d","datavalue":{"value":{"entity-type":"item","numeric-id":37543,"id":"Q37543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750320$FD7BFB59-957E-4C06-8686-687995BB18EA","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750320$EBF495D9-34E8-4DC7-A52C-3EAACB3253E1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750320$4F13BAED-7CD2-4FB7-9CDE-706D893B05E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63b5b04ed3aa0acdcae036286ca8192fe935fcbb","datavalue":{"value":{"entity-type":"item","numeric-id":3741641,"id":"Q3741641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750320$F32AC395-D352-4858-B767-1F7840F2BF42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"078e0a5ec559210a14a4145be98e18a1a255f6b1","datavalue":{"value":{"entity-type":"item","numeric-id":5677064,"id":"Q5677064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750320$9290E2A6-28BD-49A1-9686-3868D1F9109E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be9a4b27634123dce7235d0ac0c37ee1217fc4f7","datavalue":{"value":{"entity-type":"item","numeric-id":3682509,"id":"Q3682509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750320$DD70D1C4-2148-46CE-B2A4-355AE70A5684","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df152fce31faf34eee24a009426b20518b2d1c43","datavalue":{"value":{"entity-type":"item","numeric-id":3960887,"id":"Q3960887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750320$080B7599-CA91-4190-B0B3-A4C1DFA18E8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750320$AAB75A2F-A86C-4AEA-8912-9DC58444E2D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f98527e95e30b0522da5b0d1ff72ede7cfbae1f8","datavalue":{"value":{"entity-type":"item","numeric-id":1144589,"id":"Q1144589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750320$533BC49B-8319-431E-A169-9881C202D60F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5690144b5bc43388ad516c323fee78011dddefeb","datavalue":{"value":{"entity-type":"item","numeric-id":1356212,"id":"Q1356212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750320$DC050B0B-8DCD-4160-AB04-3EF86268F39E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa03fdd53c1b9f8eb1141c56fc2bb4afc212b013","datavalue":{"value":{"entity-type":"item","numeric-id":1821034,"id":"Q1821034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750320$AE791E56-D822-414D-8A14-DF283027021B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"372062ab71daaf29e9e9d082cc69fa4e57387087","datavalue":{"value":{"entity-type":"item","numeric-id":4018159,"id":"Q4018159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750320$E010216E-8A82-4563-9F33-0C2925C6DE0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86c473de4a003041033a704960e70418f4ff64d5","datavalue":{"value":{"entity-type":"item","numeric-id":753502,"id":"Q753502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750320$3ED92B91-0EAA-4D0D-89B4-F121EDCD4A78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65d469922887779d18bbf3fd4f31925af73b9db9","datavalue":{"value":{"entity-type":"item","numeric-id":1262136,"id":"Q1262136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750320$1D838FCD-2B48-4F75-AA78-A6578F549E30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f099c8af7b6bae04f2637cc914f5615498541c4d","datavalue":{"value":{"entity-type":"item","numeric-id":580987,"id":"Q580987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750320$23F789F9-6205-4670-850F-DC4E4581FFD5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6ba60f36284c7b295767fc6ec2d26da0b28a8524","datavalue":{"value":"https://doi.org/10.1016/0305-0548(90)90048-c","type":"string"},"datatype":"url"},"type":"statement","id":"Q750320$47D62F7C-DEC1-478A-9623-655CE388F438","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1a3d3f4ea248977e52d650f7774eca71d3f25f66","datavalue":{"value":"W2048440507","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750320$AF627037-7992-4105-A2A4-DAA0805F3611","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e7492682ee60aac348056b8936cb1948014a2fb","datavalue":{"value":{"entity-type":"item","numeric-id":1262136,"id":"Q1262136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"158239ec1bd7efd27e25a3a25bb869533e253322","datavalue":{"value":{"amount":"+0.8549830913543701","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q750320$3CFC5A2D-5E87-4AC2-8D2F-F426DA6FD9E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03c32a1002155eea0393409dabfb8de99570b8b2","datavalue":{"value":{"entity-type":"item","numeric-id":5687257,"id":"Q5687257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3782a801ec571fce88a96efa4b858e4d1b59dae","datavalue":{"value":{"amount":"+0.8087307214736938","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q750320$38EFFD3D-9C7B-4B43-8AD5-AF98BF2521AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0f8e35b09c0b23d3565d93699988a2b7ffbe2eb","datavalue":{"value":{"entity-type":"item","numeric-id":1328431,"id":"Q1328431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c535155bcb9a604e8483595c124338b8370060df","datavalue":{"value":{"amount":"+0.7975237965583801","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q750320$946FD29F-1FEF-432D-8096-1D06BE1509DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cf93cefca3c98fb2ce9fe849f9e00662120fb2c","datavalue":{"value":{"entity-type":"item","numeric-id":4319768,"id":"Q4319768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ba3ee3f22f7e3bcded0f43306888835db09da14","datavalue":{"value":{"amount":"+0.7939683198928833","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q750320$951FF232-DE80-448A-9487-F67B6A39AEB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f406f91889088cc3e4e2c143a2130c77451075d3","datavalue":{"value":{"entity-type":"item","numeric-id":519101,"id":"Q519101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1109ad4a0fd67a265962960116e6097c63f88df8","datavalue":{"value":{"amount":"+0.7862487435340881","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q750320$CD271608-1EA5-46D6-B73E-2E13117D71BA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:750320","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:750320"}}}}}