{"entities":{"Q1577115":{"pageid":1587855,"ns":120,"title":"Item:Q1577115","lastrevid":70743780,"modified":"2026-04-13T16:27:51Z","type":"item","id":"Q1577115","labels":{"en":{"language":"en","value":"Algorithms for graph partitioning problems by means of eigenspace relaxations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1498195"}},"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":"Q1577115$7E13A95B-00A1-4F64-A47E-A53FBD52311A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4005884d0f0ea00497d2e41ba9ec1c97508d4770","datavalue":{"value":{"text":"Algorithms for graph partitioning problems by means of eigenspace relaxations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1577115$877767A0-D97F-492B-944A-B0151C034129","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b361ed014345587a475a3b70d6d15111229f9564","datavalue":{"value":"0947.05072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1577115$E32D5854-C72B-41D4-8830-30422089451F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0c26139466c88bfe198ea097e09a33db8b3abaaa","datavalue":{"value":"10.1016/S0377-2217(99)00060-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1577115$3D2A9949-030C-4D45-A83C-77B1E2575A29","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a425c7f94a28cc4046a3697c77561e45e2f7f285","datavalue":{"value":{"entity-type":"item","numeric-id":1406653,"id":"Q1406653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577115$97B43BB1-4CB1-45C6-BCBB-079CA59814E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9250f6224975305b0e3a4df3806eb864937967df","datavalue":{"value":{"entity-type":"item","numeric-id":612744,"id":"Q612744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577115$B9A74B5B-1BA6-426F-A68A-B7A8ACFAD85E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca557a17e8d7f3be926e16836adc90ecd87e837d","datavalue":{"value":{"entity-type":"item","numeric-id":1282130,"id":"Q1282130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577115$1DAC5128-332F-4C66-8F06-1E3F4645A3B8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38576f39a6df37711cb397d1408ced7e3814cc6e","datavalue":{"value":{"entity-type":"item","numeric-id":62319,"id":"Q62319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577115$DCC59C52-4A35-4365-8E86-BA85F6E7B7D8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6586588445949d2fbb40c4309ca2cd89ad6a7878","datavalue":{"value":{"time":"+2000-08-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1577115$DBBF26E4-6A9A-46AC-9F4C-BD960C0751AC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"85196e6d04cadaffc9b921a3f176fe989c6a9500","datavalue":{"value":"The authors investigate the problem of partitioning an edge weighted graph into \\(k\\) connected components so as to minimize the weight of the edges between components. They propose an algorithm for the problem based on eigenvalue methods. The connection between this problem and semi-definite optimization and eigenvalue bounds is well known and therefore the performance of algorithms based on such bounds is of current interest. This paper uses the Donath-Hoffman bound (which is computed by a subgradient algorithm) and a variant of an algorithm by Boppana. Computational results are provided.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1577115$EF2EF91A-2C99-4BA9-8E3A-66CB56ADE15A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1577115$63A43D4F-C9CC-4587-B38B-3E7ECBCFC42E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1577115$D0120BD7-543D-455B-8CC9-CB8802B8C088","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"496a2262c4928f67cf3c8604d786b45783aef503","datavalue":{"value":"1498195","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1577115$98132969-2675-4D0C-90DC-1A32A347B253","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e242af08a265f147fecdde71acc893f1df2b816","datavalue":{"value":"graph partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1577115$EFE2A90F-9D76-493D-9283-F14952DF9657","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"811604a75801fcd709c8667f83ea26944825b8d2","datavalue":{"value":"eigenvalues","type":"string"},"datatype":"string"},"type":"statement","id":"Q1577115$673E1D10-6D39-4C00-8F60-CB8342F5E93A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf82c91ec263367c502b2e0283c705fb0e3dd3ec","datavalue":{"value":"\\(k\\)-cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q1577115$578070E8-4121-45C0-9B4A-31CA6B3E9736","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"410981a1afadda812bc680dfed4766e5e039a80f","datavalue":{"value":{"entity-type":"item","numeric-id":581215,"id":"Q581215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577115$59F0509D-ECC8-4A97-871D-DA4E3C53242F","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":"Q1577115$6BD50B48-5B31-487C-B8B4-DC50096FF733","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"08df152080249f51aeb11009adb6df7d097b7d34","datavalue":{"value":{"entity-type":"item","numeric-id":4740598,"id":"Q4740598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577115$28B1120A-0D89-4E2A-ABA5-71F94A4B7ECB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6773d6b15d1344c7dac2343b32974c7313d44578","datavalue":{"value":{"entity-type":"item","numeric-id":3338296,"id":"Q3338296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577115$BAE3C751-44EC-4BC3-BC80-A8C7F63BD50B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"995f3d0e21cb6132e6a7dfc3313fc18917a919c4","datavalue":{"value":{"entity-type":"item","numeric-id":3802647,"id":"Q3802647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577115$E2EC308D-41AA-4475-A054-6DA3BE2BED72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"131dbfa8457f88efb04bf2a7feb513ebf8d4dc80","datavalue":{"value":{"entity-type":"item","numeric-id":4127646,"id":"Q4127646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577115$A76675F1-8D0A-4F4C-BD8D-168B7EC84E95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0695897ba1f4d354cee59bd513998e8d8e9377a3","datavalue":{"value":{"entity-type":"item","numeric-id":5675744,"id":"Q5675744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577115$93B21EB6-0932-4B34-8085-92022BBB1688","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbd6b78d3237f96404fbe2b11b011d2949a400f4","datavalue":{"value":{"entity-type":"item","numeric-id":1340061,"id":"Q1340061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577115$81533AD8-8475-4C3A-928F-D791B95F5C43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577115$C7F94A1D-673B-4928-BA36-3CBC1703788D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ced5cfe1b079ebdc8de66d106a03be7ec616709a","datavalue":{"value":{"entity-type":"item","numeric-id":3359644,"id":"Q3359644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577115$C1719FC5-8757-4F65-BC8A-D74CDC68C6E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"611d370f15cf0c70efce53dab16cc6e7fee5248a","datavalue":{"value":{"entity-type":"item","numeric-id":1103410,"id":"Q1103410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577115$596B1E42-9673-4814-B5B8-C7B136DF96A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa61779986dc5385db6d3e154b67a8b541e8c491","datavalue":{"value":{"entity-type":"item","numeric-id":4022029,"id":"Q4022029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577115$ABEA7BE6-3682-4FEF-9DFB-AACAE1865342","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"792438f7abc016f160ebe3f253bd2a015467979e","datavalue":{"value":{"entity-type":"item","numeric-id":2650944,"id":"Q2650944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577115$1F860637-F590-4B56-9D43-4B5B92ACEDCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a44f31abbdd4dc84e5f661896a7812e44411ddf","datavalue":{"value":{"entity-type":"item","numeric-id":4100093,"id":"Q4100093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577115$EC6867E1-4E68-47CD-91C2-B85085EE2D5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e579aa4704eaeaa9ad5064e4744c9d902a73e187","datavalue":{"value":{"entity-type":"item","numeric-id":3997942,"id":"Q3997942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577115$E11029F2-84F0-431C-BFF1-C08986572F26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e627512a063f8909b9161f05ca4719139a48cb1","datavalue":{"value":{"entity-type":"item","numeric-id":5331504,"id":"Q5331504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577115$48B05721-EE8B-4A86-BA01-89E038EE289D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a3a6cc8ab159ddcfcba4ce8cc1a6d6a97ea1bb8","datavalue":{"value":{"entity-type":"item","numeric-id":3138918,"id":"Q3138918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577115$815D9AC1-34E0-4722-B5D5-082438D1FD43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14fb0962ec1970cd24de49d8536c8bbd1a39fa82","datavalue":{"value":{"entity-type":"item","numeric-id":1904714,"id":"Q1904714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577115$73B94671-5B65-49E1-B1F4-3C16FD245DB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a34d06cb94a1bbb222c34a80d362cf924c6066f","datavalue":{"value":{"entity-type":"item","numeric-id":1406654,"id":"Q1406654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577115$B00BB0FA-EE97-43A4-896A-810B29F3E849","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e62fbb600f701c41c2647894d98ae87726391b2a","datavalue":{"value":"https://doi.org/10.1016/s0377-2217(99)00060-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1577115$7D142DDB-E7AD-4D62-BF5D-C8D6F28DBC6A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a0d82b3f03ffdc3c7d3dc7c121e07c62a2d9f4ad","datavalue":{"value":"W2022619737","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1577115$7E0ECA49-F042-47F7-A1CF-464992818D65","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb8fcff870ee61f27a9967fbc404f6b5c74bcf27","datavalue":{"value":{"entity-type":"item","numeric-id":1340061,"id":"Q1340061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2e1b4d649bd0c82fc3bc043126942e17e6ce86f","datavalue":{"value":{"amount":"+0.8682565093040466","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":"Q1577115$4DB0455E-8EED-48D1-BBB1-2E5C507AA368","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee779b0503591c4a32233900db32c5e56bd4a9ed","datavalue":{"value":{"entity-type":"item","numeric-id":3142604,"id":"Q3142604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c629d7f419a735c4973c9d303bab47abbb4ebf1d","datavalue":{"value":{"amount":"+0.848700761795044","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":"Q1577115$6874BE0C-92C7-40DB-8769-1F055ACDB380","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"013b3c2dd5fb92916093e188ef9b571dd68c4f6c","datavalue":{"value":{"entity-type":"item","numeric-id":1942271,"id":"Q1942271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12c3ba590b6121ea6a2b649861f2e383df572119","datavalue":{"value":{"amount":"+0.83721524477005","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":"Q1577115$54656CCA-84AB-475E-89BF-A6241F6C512C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eae30e12ee6338a10524c29ade58fab9b846007a","datavalue":{"value":{"entity-type":"item","numeric-id":4326662,"id":"Q4326662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4d6235e44f581fbbcc8537de9f934a9d6cc96fc","datavalue":{"value":{"amount":"+0.8284351229667664","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":"Q1577115$31466DC0-B05B-466A-928F-DA7AA103F4D8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Algorithms for graph partitioning problems by means of eigenspace relaxations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Algorithms_for_graph_partitioning_problems_by_means_of_eigenspace_relaxations"}}}}}