{"entities":{"Q1868840":{"pageid":1879582,"ns":120,"title":"Item:Q1868840","lastrevid":73593426,"modified":"2026-04-14T16:35:00Z","type":"item","id":"Q1868840","labels":{"en":{"language":"en","value":"Linear-time recognition of bipartite graphs plus two edges"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1901892"}},"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":"Q1868840$E9824B35-39A1-4FEE-9E89-76E48B06C594","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"94817e2b734f3c6b2d033684d6017c09d40a751a","datavalue":{"value":{"text":"Linear-time recognition of bipartite graphs plus two edges","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1868840$3DC12CFC-AB6F-4F9B-BE62-1B1AEBE1D44D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2bb7283a9a9506c22452b3d848e764a4aa128feb","datavalue":{"value":"1012.05146","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1868840$B0D885B3-82DA-4B9A-ACA7-129D749E5629","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4c64560ebe4286ba5de55b281afce1b2fed00904","datavalue":{"value":"10.1016/S0012-365X(02)00493-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1868840$4C3B1F79-A6F7-4944-95C5-4DC3EBE18511","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"efc35cf3e0639840fea360bd5e9b46c46abc9a77","datavalue":{"value":{"entity-type":"item","numeric-id":169283,"id":"Q169283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1868840$40F0AA58-CE02-4894-80E7-D62F37B27930","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1868840$407337CC-BF92-4346-BACA-1EFEB7509D63","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3b05751a28df8b7d171e02c18dec5082d33efa41","datavalue":{"value":{"time":"+2003-04-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1868840$E2CB1622-B883-4277-8336-B37E21F1E683","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"db64864b9e559db0419e0e7240f5245d9ada59cb","datavalue":{"value":"This paper marks a second step towards a fixed parameter algorithm for MAX CUT. The first step was done by \\textit{L. Cai} and \\textit{B. Schieber} [Discrete Appl. Math. 73, 27-34 (1997; Zbl 0867.05066)] who proved that bipartite graphs plus one edge can be recognized in linear time. Several edge deletion problems like feed-back arc set are fixed parameter tractable due to the general Robertson-Seymour theory. This does not apply here since bipartite graphs are not closed under edge contraction.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1868840$043A58BD-909F-4B14-ABDC-01BE49EC8632","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1868840$65D0A46E-AF51-4BD5-ACD5-9C29644F290C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1868840$9780ABF6-F676-47EE-A884-6DE38B037F63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9ed1e3c6cced595a05b8ae19055521b22405b78a","datavalue":{"value":"68W99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1868840$2F5FA093-6DDC-45BC-9996-ED6AD9C0D934","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1868840$C18D7A15-2BC4-41EA-A878-82910A60F293","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f628d54208f264e86e80f28f92e0d1d9c19ffce7","datavalue":{"value":"1901892","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1868840$0809940C-1D49-49C1-AD3B-6A14C9066C42","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a38b11968d7cb86be0842b661cd5bdd713115f5","datavalue":{"value":"graph algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1868840$4B5F2E62-B7DF-423F-89FE-3686B23DA894","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"618b7b4529f3e6f820c6bc9ffeaa17a7d6c28978","datavalue":{"value":"depth first search","type":"string"},"datatype":"string"},"type":"statement","id":"Q1868840$938913EC-8DFC-4D69-A4E7-8735E50A7A09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a240bc2cb59effa1768d42a8e0af03ff1afb7af","datavalue":{"value":"parametric complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1868840$0E3DBB5C-1AEE-47E5-9DB5-EE28B119998B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"103c4183f41a81aa3daa604f2d8b1063f6d282e5","datavalue":{"value":"recognizing graph properties","type":"string"},"datatype":"string"},"type":"statement","id":"Q1868840$007F1351-C036-40D1-9935-031B34239717","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"686448fd2e9d2db11f4901a1870c55c52d2d4052","datavalue":{"value":"max cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q1868840$A3C1CEB9-4626-4400-843D-3D58CBD4734E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5186fd99999e6921db65766363ee98e6a615dadc","datavalue":{"value":"linear-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1868840$E014B7C5-3BA4-490F-99C8-CE4099AA8736","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":"Q1868840$04964938-E7AA-475A-8AEF-C6323EB55573","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9b8bf34248127885aa8004781e265e82c2b40aa2","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(02)00493-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1868840$3D8B7C0F-FB88-4A94-B136-C624A8C51255","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6733f192bb211b15e346a828cb65007761a274e5","datavalue":{"value":"W2016921924","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1868840$3EBB5F5F-940E-4890-9795-5F564EECB15B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c4acd401c156467d4bb8ec0c54706c28be71e92","datavalue":{"value":{"entity-type":"item","numeric-id":4634410,"id":"Q4634410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c30a6bef3104e9f5345baba82e5007050528ea50","datavalue":{"value":{"amount":"+0.76961350440979","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":"Q1868840$9625BCB7-CA50-4E1F-9AE2-F795EF11C416","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1adbbdd2d76b31a4288b45d42f67efedb0f99a54","datavalue":{"value":{"entity-type":"item","numeric-id":4290088,"id":"Q4290088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5676549ffff30687719a57de53f3ebd28bdb450","datavalue":{"value":{"amount":"+0.7694368362426758","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":"Q1868840$269004FC-C5AC-418A-994F-F32156EC0176","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75878f0dc394f4e6cdeb914b358d471d4407769e","datavalue":{"value":{"entity-type":"item","numeric-id":3043700,"id":"Q3043700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5676549ffff30687719a57de53f3ebd28bdb450","datavalue":{"value":{"amount":"+0.7694368362426758","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":"Q1868840$C6E2DFA3-372C-435E-93ED-554905D12FB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c839ece2498323980f019a565235abf4647f924","datavalue":{"value":{"entity-type":"item","numeric-id":666655,"id":"Q666655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29a46f46c84600796320741362184dbb670a57f5","datavalue":{"value":{"amount":"+0.7670187950134277","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":"Q1868840$0F5BD500-FE62-47A6-BB03-9B561B72D024","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a489c3fea9b922c65ac59389c60d3b9a745b2f9","datavalue":{"value":{"entity-type":"item","numeric-id":2482113,"id":"Q2482113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3dca1841c8bade2ee2a27018a49212984feface4","datavalue":{"value":{"amount":"+0.7616008520126343","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":"Q1868840$911F216F-75AB-4A14-B4F6-295EF54E3E10","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Linear-time recognition of bipartite graphs plus two edges","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Linear-time_recognition_of_bipartite_graphs_plus_two_edges"}}}}}