{"entities":{"Q1198016":{"pageid":1208765,"ns":120,"title":"Item:Q1198016","lastrevid":66846921,"modified":"2026-04-12T13:15:20Z","type":"item","id":"Q1198016","labels":{"en":{"language":"en","value":"A linear time algorithm for graph partition problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 92086"}},"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":"Q1198016$56B21157-DA94-4819-9EDB-D8E00FB4FB9A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7b4a340dff248e2fefdb3b1772ee913d67dbe90b","datavalue":{"value":{"text":"A linear time algorithm for graph partition problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1198016$6727F771-D665-445E-9DB6-09122EFD3581","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"22d0b2ca3390cc23a8eb5bd312666a0a9c2979ad","datavalue":{"value":"0765.68045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198016$0F0A839F-B3A8-4F92-ABC1-BEA23CD20B7E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"619deeb21c7e4f567032f3601e5cc2a4587bca14","datavalue":{"value":"10.1016/0020-0190(92)90126-G","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198016$4569C154-67A2-42D5-A8B8-69CB65289CD6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198016$A955C52F-9DB3-4EE4-AF01-3753ED474096","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1198016$82434697-BCE8-4964-9FA3-D219536FDD8A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"90c20a53597d5e6fc7fd57e5dda5199274efaef1","datavalue":{"value":"We present an \\(O(| V|+| E|)\\) time algorithm which partitions the set of vertices of an undirected graph \\(G=\\langle V,E\\rangle\\) with maximum degree \\(\\Delta\\) and minimum degree \\(\\delta\\) to \\(\\{A,\\bar A\\}\\) such that the following hold:   (i) The number of edges with one end point in \\(A\\) and the other end point in \\(\\bar A\\) is at least \\(| E|/2\\).   (ii) The difference between the number of vertices in \\(A\\) and the number of vertices in \\(\\bar A\\) is 0 if \\(| V|\\) is even, and is 1 if \\(| V|\\) is odd.   (iii) The absolute value of the difference between the number of edges with both end points in \\(A\\) and the number of edges with both end points in \\(\\bar A\\) is at most \\((\\Delta-\\delta)/2\\) if \\(| V|\\) is even, and is at most \\((\\Delta+1)/2\\) if \\(| V|\\) is odd.   The partitioning algorithms for which (i) and (ii) hold are known, see \\textit{M. K. Goldberg} and \\textit{R. Gardner} [Progress in graph theory, Proc. Conf. Combinatorics, Waterloo/Ont. 1982, 295-305 (1984; Zbl 0559.05059)]. However, we are not aware of any algorithm for which (i), (ii), and (iii) simultaneously hold. Section 2 contains our main results. We describe our algorithm which has running time \\(O(| V|+| E|)\\) and \\(O(| V|^ 2)\\), for unweighted graphs and weighted graphs, respectively. Our algorithm is a modified version of the algorithm of \\textit{C. H. Papadimitriou} and \\textit{M. Yannakakis} [(*) Optimization, approximation, and complexity class, Proc. 20th ACM Symp. Theory Comp., 229-234 (1988)] for approximating the maximum cut problem. We remark that for the cut generated by the algorithm in (*) property (i) holds, but properties (ii) or (iii) may not hold.   In Section 3 we describe the applications of our algorithm to three NP- hard problems: the maximum cut problem, the graph bisection problem, and the bottleneck bipartite number problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198016$643222EC-A9EC-4D49-A56E-7AF4E8C87318","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198016$CA4C9246-8A75-4025-BC6F-41CE888DB6A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198016$323C3176-B650-408D-A9E6-809AA1598318","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ea74a400f1dc611bd28c15a00210ffddf87a50d3","datavalue":{"value":"92086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198016$D14858D2-9758-46FE-A14F-08FB6885BDCD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c27a8414208eba22b391b2c3a982e6e5e1d84b","datavalue":{"value":"linear time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198016$A0EB8AE1-75A3-45E6-90B3-748FAAD0737F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51a4d2f184eb71178bc677bcea7c20cd074b818c","datavalue":{"value":"graph partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198016$FA800930-1E57-44C7-999D-3187B11B64C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bc8e8369a826e4b6a904df25885da5a26b9eec8a","datavalue":{"value":"partitioning algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198016$E8895D5C-3804-4854-93DB-104855CAD626","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3a9cb49c87f60d83547600e005cf06abd319283","datavalue":{"value":"maximum cut problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198016$B325936E-A964-4A8D-A1A0-19673FA5BDF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8723a926a0441e6756ef1c46346614580e790282","datavalue":{"value":"graph bisection problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198016$5B5921FB-F6B7-4856-9F23-DA8D53DDCF89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"83455aba716129afb6b240cde65bd6f139960a0e","datavalue":{"value":"bottleneck bipartite number problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198016$5C307C28-5B59-4D5D-8327-14761C85CD90","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e38d7a3cac136d69e468e7b2bb350158b51e7413","datavalue":{"value":{"entity-type":"item","numeric-id":1363710,"id":"Q1363710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198016$A9D1F851-5C68-4B6B-8BA0-65A264499718","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"25f1cfa3980c3cfc230dee260e62cad57d59a417","datavalue":{"value":{"entity-type":"item","numeric-id":169303,"id":"Q169303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198016$2FCE1ADB-E959-46C0-995A-70C795AD99A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c1337363d3ae6a5841e776ab4e68a03f2d64d151","datavalue":{"value":{"entity-type":"item","numeric-id":169304,"id":"Q169304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198016$C7631905-0AD5-439B-8D43-887AF12BE68C","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":"Q1198016$002F5DB4-B116-4BB4-B8A7-11EC43BC941E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"72bdc200c096a90cb093d01083b69c58672a0aa3","datavalue":{"value":{"entity-type":"item","numeric-id":3682518,"id":"Q3682518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198016$D0BAF2E2-1437-4C43-B8CC-A4B2C6A1F133","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5da3b54f7ef8a2117279ae6dffad9f5ec74f16a9","datavalue":{"value":{"entity-type":"item","numeric-id":3818315,"id":"Q3818315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198016$D2ABB43C-C06C-4936-9D20-32AA2692AB6F","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":"Q1198016$8266C5EE-600B-429B-BA7B-42F0BC0FD603","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"645b2999f4ba18733e6680c85fa03c214cb4fbea","datavalue":{"value":{"entity-type":"item","numeric-id":3347934,"id":"Q3347934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198016$85E179D1-27B0-4E99-8301-15D6C00E87D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0a3018c1d9d608381b99fb755b36cda280b1e61","datavalue":{"value":{"entity-type":"item","numeric-id":810053,"id":"Q810053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198016$2FC94BDC-565D-488A-92B8-B334B3B517D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198016$F853AB29-2217-43F3-831C-86D7A6DF073C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58b75e823d7d97463bea3f1b237ecc88aaa499fb","datavalue":{"value":{"entity-type":"item","numeric-id":3474283,"id":"Q3474283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198016$86D737F6-31CB-447B-B107-6BF801318462","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df89ac7148e67334b60ab872cad32bf98faef00c","datavalue":{"value":{"entity-type":"item","numeric-id":1198016,"id":"Q1198016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198016$ECB5FB1C-BCBC-4B56-951F-12AFEB6A7294","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc6e689ca9104617943bd76b284824e0c9ceb6bd","datavalue":{"value":{"entity-type":"item","numeric-id":3707420,"id":"Q3707420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198016$B6051E76-FA11-4A6C-8A6D-BCB25300CDE2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"db4eec31b68418a4af21fc42394d3773544c8543","datavalue":{"value":"https://doi.org/10.1016/0020-0190(92)90126-g","type":"string"},"datatype":"url"},"type":"statement","id":"Q1198016$C76AB67D-EBB7-46DC-8377-F4BE6DB6A3CE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7d3fb83d5d1cd4a987ff7b809203c8c174f47040","datavalue":{"value":"W1991957444","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198016$39C410F2-4860-451F-BD95-D750EA385C87","rank":"normal"}],"P1643":[{"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":"a7a7e88af7cf85f2af2611dc8664a269fd6dafa6","datavalue":{"value":{"amount":"+0.9393603","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198016$4221F19E-F282-4857-8270-DEDCFFC5D556","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12c3a07d8d0126493e14efe4242033f196e8c152","datavalue":{"value":{"entity-type":"item","numeric-id":4511245,"id":"Q4511245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ffa1e38e215170805974e0e506038b277095a70","datavalue":{"value":{"amount":"+0.93598366","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198016$395493C4-968E-4EED-B49D-08B005C62AE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44dee836927bf1ed3e26dd3f286508f7451f7597","datavalue":{"value":{"entity-type":"item","numeric-id":3580949,"id":"Q3580949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c224c776d2a3add70fec7955dcffa04b646dee94","datavalue":{"value":{"amount":"+0.93554634","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198016$66EE0D8A-AE9A-43D4-B081-6A2672F2E5C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58e84031af636802206d2bfb11839131d98d0eff","datavalue":{"value":{"entity-type":"item","numeric-id":3717092,"id":"Q3717092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d8f8a334662a738fe93119283f23a1d15d588b1","datavalue":{"value":{"amount":"+0.9350828","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198016$CD3CF515-E4D3-4AA0-923E-67B9312E07A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc6baefa02a74b7737c3b93aa8bf28c0e3e1c500","datavalue":{"value":{"entity-type":"item","numeric-id":1411631,"id":"Q1411631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e413e76bb26f130f890657adfce277b66006c13","datavalue":{"value":{"amount":"+0.934706","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198016$4A2673BD-B40D-45C9-85CF-F88E4ECA77AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d14eff9d380f039b0b4b904c5736a78b972e4455","datavalue":{"value":{"entity-type":"item","numeric-id":3835330,"id":"Q3835330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5eca767546def9199095a4e60fbfd9fba507625c","datavalue":{"value":{"amount":"+0.93424386","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198016$9EAA91E0-5807-480C-82F8-35B3E5221EEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7964673ffa899ed3b0947e69d5b249da42be375a","datavalue":{"value":{"entity-type":"item","numeric-id":6080366,"id":"Q6080366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b93cd0aa883bc105ca745158d07727eaffc27b5f","datavalue":{"value":{"amount":"+0.9325236","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198016$6A2997CA-4A74-40C5-B755-F4031B163AF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a564a6a587d94eee4cd9d5725bec5d2dc321428","datavalue":{"value":{"entity-type":"item","numeric-id":4526868,"id":"Q4526868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d6d67f88556eabf01f9dfca8ec7f604a8978978","datavalue":{"value":{"amount":"+0.9318588","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198016$2702D8F8-FE83-43D2-9FB5-BD149D750D70","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A linear time algorithm for graph partition problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_linear_time_algorithm_for_graph_partition_problems"}}}}}