{"entities":{"Q6828271":{"pageid":15109567,"ns":120,"title":"Item:Q6828271","lastrevid":56007925,"modified":"2026-02-24T13:05:10Z","type":"item","id":"Q6828271","labels":{"en":{"language":"en","value":"Approximation algorithms for connected maximum cut and related problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7179873"}},"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":"Q6828271$D6BB7834-F7CF-4CE8-A14F-6433A91A9215","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4223c867c5c393ca5b5034af21e695dedc9b2faa","datavalue":{"value":{"text":"Approximation algorithms for connected maximum cut and related problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6828271$21D13B30-C2EC-4AA7-ABC4-C5A7601B0D53","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6d981730a1373dcc03fc77e1b58c4160a4638378","datavalue":{"value":"1445.68166","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6828271$8FF7711E-2854-4194-A390-231A6BB61710","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1f38b11374b3d26840b2662e4dfd04078ff8ba64","datavalue":{"value":"10.1016/J.TCS.2020.01.016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6828271$761B245F-85BC-4135-BB2B-D5822F8CAF43","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3098471736f417aa552d69c3165075e7ba3a336f","datavalue":{"value":{"entity-type":"item","numeric-id":487271,"id":"Q487271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6828271$EB6722B3-ED8B-4FCB-A0B5-43B0B593D8F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ad027b94ac02d4587dddeddcfc38c6e10541f29d","datavalue":{"value":{"entity-type":"item","numeric-id":260246,"id":"Q260246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6828271$DF7864D9-7DBE-489C-A083-81F81A9D49CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"108bcbbed82c01a8cf5e0748070831abf5042fde","datavalue":{"value":{"entity-type":"item","numeric-id":2304551,"id":"Q2304551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6828271$9B9775FC-1A6D-4ED1-A926-7ABE41A6700B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0bf959f67f15929577fc91fe7a70a9e277fd0864","datavalue":{"value":{"entity-type":"item","numeric-id":2211359,"id":"Q2211359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6828271$FD79AE11-D513-4727-89D5-3CE34D6B49A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e52edaa51a61b49c83799dc8dd5f6de927ced9a9","datavalue":{"value":{"entity-type":"item","numeric-id":270000,"id":"Q270000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6828271$18A8F2BD-89E8-409B-A5BA-4472DE16C632","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6828271$21027F78-C931-4040-A666-64845F955BD3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a3ddeab2841725759b2e820b7ea1589750ac80ae","datavalue":{"value":{"time":"+2020-03-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6828271$FC6A8C9A-DDAA-4915-AC90-96D28B659931","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"be354c2be5478074ea00f1ad3e805ee6529f7f38","datavalue":{"value":"The paper obtains new results on the Connected Maximum Cut (CMC) problem, which is defined as follows: given an undirected graph \\(G =(V , E)\\), the goal is to find a subset of vertices \\(S\\subseteq V\\) that maximizes the number of edges in the cut \\(\\delta(S)\\) such that the induced graph \\(G[S]\\) is connected.\\N\\NThe principal results are:\\N\\N1. The first \\(\\Omega(\\frac1{\\log n})\\) approximation algorithm for the CMC problem in general graphs. The authors employ a novel approach which is to look for \\(\\alpha\\)-thick trees, which are basically sub-trees such that leaves of the tree have a large degree in the original graph.\\N\\N2. An \\(\\Omega(\\frac1{\\log^2 n})\\) approximation algorithm for the Weighted Connected Maximum Cut problem. The basic idea here is to group the edges into a logarithmic number of weight classes and show that the problem on each weight class boils down to the special case where the weight of every edge is either 0 or 1.\\N\\N3. A polynomial-time approximation scheme for the unweighted CMC problem in planar graphs and more generally in bounded-genus graphs. This comes with the help of a stronger form of the edge contraction theorem by \\textit{E. D. Demaine} et al. [in: Proceedings of the 43rd annual ACM symposium on theory of computing, STOC '11. New York, NY: Association for Computing Machinery (ACM). 441--450 (2011; Zbl 1288.05256)].\\N\\N4. A proof that the CMC problem remains NP-hard even on unweighted, planar graphs. The proof constructs a polynomial-time reduction from a special case of 3-SAT, called the Planar Monotone 3-SAT (PM-3SAT), to the CMC problem in planar graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6828271$EAAC8A5A-8D0E-4E4C-9A89-12E7732FB472","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d7f1127c63fcb04479eae252afd6f073fe30fe10","datavalue":{"value":{"entity-type":"item","numeric-id":187117,"id":"Q187117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6828271$AAAC6F0D-138B-4EC5-A6EF-6666B0C2742D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6828271$DDFC09B7-4334-4012-AF66-4A0D2F83426A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6828271$117C1A88-E971-4552-A7B5-7ED0CBF1DB5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6828271$369C9535-2416-473F-8E53-91CA2C95DAA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6828271$F69C9017-1122-4E08-84A2-68CCBB4CA790","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6828271$8873BC33-B8A5-43CA-8B46-AFB3991791BC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e11a423a01012a989b4a7f801ba129ef99a42c48","datavalue":{"value":"7179873","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6828271$61B6FF3E-6B69-49B5-A39F-34378C1896B2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q6828271$AE9BAEF7-C523-46A1-85E5-F9E87520FFF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c91f31ff3148cef663c71257dfee794b67d236ff","datavalue":{"value":"connected maximum cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q6828271$6FBBDC40-0A77-481E-8C45-1E6172976EDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4189a2526f84a72041084c5bdd596805602dd44","datavalue":{"value":"connected submodular maximization","type":"string"},"datatype":"string"},"type":"statement","id":"Q6828271$E57AF17B-624A-4A26-A986-4D9C280EDB5D","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":"Q6828271$C9C5740F-73A4-4039-9F07-A2FC33F3F3FA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Approximation algorithms for connected maximum cut and related problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Approximation_algorithms_for_connected_maximum_cut_and_related_problems"}}}}}