{"entities":{"Q5935599":{"pageid":8112401,"ns":120,"title":"Item:Q5935599","lastrevid":40908353,"modified":"2025-04-14T00:55:47Z","type":"item","id":"Q5935599","labels":{"en":{"language":"en","value":"Efficiently recognizing the \\(P_4\\)-structure of trees and of bipartite graphs without short cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1610693"}},"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":"Q5935599$6F2FF4C5-CE99-4CCE-A83D-E848F9E55034","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"482dc177382dbf6cf1c0de1c61bdd3eba3f77ff0","datavalue":{"value":{"text":"Efficiently recognizing the \\(P_4\\)-structure of trees and of bipartite graphs without short cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5935599$A9B75BDF-23C7-4AE1-B114-DBE6D833A7B7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"de2c0f732faad0ddefb45448313488ecea7f231a","datavalue":{"value":"0998.05038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5935599$8F1565AC-CF56-4439-9625-C42827CF5FF7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bbb68d9de22321af7fb543db220c0a16a741857c","datavalue":{"value":{"entity-type":"item","numeric-id":170457,"id":"Q170457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5935599$5C943FA8-E5AE-4FC9-9CBA-CD688B4D4810","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d58268156f8ce664e47b92662ca397a022d5f810","datavalue":{"value":{"entity-type":"item","numeric-id":185062,"id":"Q185062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5935599$AD410A89-C813-4F7A-8504-65ECB8D25257","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3e7020a54266d4b2ab3b7f83a2814036c1ab56ec","datavalue":{"value":{"entity-type":"item","numeric-id":185063,"id":"Q185063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5935599$FA9744AB-9B9F-47EA-B35F-984DD6B22DB0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5935599$64E64CFD-7769-4295-8892-C103208E7B9B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"51fa866876a61ae2435740199de51e5bb1a31ee7","datavalue":{"value":{"time":"+2000-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":"Q5935599$EF15E61E-F876-4D77-A292-637865EF999A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ada7d2d687363d60aeae20da91dac1ad84709233","datavalue":{"value":"The \\(P_4\\)-structure of a graph \\(G\\) is a 4-uniform hypergraph whose vertex set coincides with the vertex set of \\(G\\) and whose edge set consists of quadruples of vertices that form induced 4-vertex paths in \\(G\\). The authors propose a simple algorithm deciding if an input 4-uniform hypergraph is a \\(P_4\\)-structure of a bipartite graph without cycles of length 4 and 6. The running time of the algorithm is quadratic with respect to the number of vertices of the input hypergraph. In the special case of trees the algorithm has a better running time than other algorithms known to date.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5935599$963DC27A-035E-4E7D-97A2-D5218BCB20DC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2e24c05a8d3e4c23a551354bc6bd226b3d93e379","datavalue":{"value":{"entity-type":"item","numeric-id":298334,"id":"Q298334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5935599$33D3F7CF-6140-42D0-864B-9DBA706BF25B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5935599$89EECD80-082E-48C9-A046-2FDB51C48064","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5935599$04184E89-3252-4615-B1DD-8B16AB0851C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5935599$9E7A5695-CCED-4A63-8712-70E067B73D0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5935599$D00420C1-A272-4494-9BB5-00483823DE0B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3e1f166393e512980e477b8093dcb2cf4e30ca21","datavalue":{"value":"1610693","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5935599$9AC99EA7-716B-4792-943D-956CA9824BD9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3187e84c5efaed03d0bd9515713a70084404d3ee","datavalue":{"value":"bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5935599$A126D890-2D10-4C6A-8C74-B429542417F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6072fa2abea179a7709e57b96ad2802601bb845","datavalue":{"value":"perfect graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5935599$AED54380-CDCD-4EDA-8C31-EB58DF5FE4BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de0a83f1e378511032f04c0ed504393e3c22a03b","datavalue":{"value":"uniform hypergraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5935599$F3468CB7-4DDA-44B5-A16C-C9E913D975E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1e5f033562cd95820974e6af42f05c5ed4c0ace","datavalue":{"value":"\\(P_4\\)-structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q5935599$3B379F2E-9A4D-4942-B915-F3F1D5434194","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e865dcf04feef79efcf163ac054d2ac37b7305b","datavalue":{"value":"paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q5935599$50E1A748-DE35-4E6A-BBF6-E9BF3E7FF46E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dcf267cbc3e04fdcfc3d3761f7ad8ebdabe8c51","datavalue":{"value":"cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q5935599$E635A1C9-FFA3-4D73-BD36-1878F3A07E55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5935599$A7D57622-B7F3-402D-80D8-C014BA435E5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c24938459dbf20196734dcf6c3a35c8a8724abee","datavalue":{"value":"trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q5935599$D34D758E-A9EE-4A0E-BA12-7C96D3FA0BB6","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":"Q5935599$5DB34143-316A-48F6-9650-84819BF03D9C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"823dc14b2af39de5849eb9d2f52d44f7f5399786","datavalue":{"value":"https://doi.org/10.1007/s003730070002","type":"string"},"datatype":"url"},"type":"statement","id":"Q5935599$282FE8E3-D40C-4FC5-9705-F4CA584C06C5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bf44855e8a1b4ef0202cedb3bed738499c92a9d0","datavalue":{"value":"W1996773256","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5935599$21BB7DE7-6EEC-4791-8035-79E00610DC78","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"03819030fd37b9248a90163253b1a420f6996adc","datavalue":{"value":"10.1007/S003730070002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5935599$595EA552-6722-4846-BB32-84A83049F7B4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"309a6e1a04a902c52672a69fd6955b87d9295f7d","datavalue":{"value":{"entity-type":"item","numeric-id":1296570,"id":"Q1296570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00db84233fdaffa8778a50d06f78cd6754fac73a","datavalue":{"value":{"amount":"+0.9182107","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":"Q5935599$F10B76DE-F6A3-444E-BBED-6F89FCCF1CE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e8b53cda601b76d31513aa3440992ef471305cc","datavalue":{"value":{"entity-type":"item","numeric-id":1343225,"id":"Q1343225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cfacc5d65d6284f07a7446edacda6e6c7f2bf07c","datavalue":{"value":{"amount":"+0.8913335","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":"Q5935599$47170244-7AEE-49A3-8C78-443BF81A1D0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c268bcd3fc809a7d0301b97ca3a159fbb02678ed","datavalue":{"value":{"entity-type":"item","numeric-id":1962050,"id":"Q1962050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"144f22ffcab33e404e57119e506ff0879d3c873e","datavalue":{"value":{"amount":"+0.8846868","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":"Q5935599$2C893DF1-1C46-47BB-8D19-4B11D3728CA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3927b675454020a273bec20f364cc8d6af1d539","datavalue":{"value":{"entity-type":"item","numeric-id":5387659,"id":"Q5387659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04bf0e36c0c9bb6e8bf98a8538e4c6954a81dcd4","datavalue":{"value":{"amount":"+0.8793462","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":"Q5935599$742A6A47-97C3-42F5-B5C0-18EBDD6F3A2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"052621bfe8c0c2672fee0f55765e69f634778ca7","datavalue":{"value":{"entity-type":"item","numeric-id":673108,"id":"Q673108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a9cf0f68bd01e4d859133b21283abaccac46c9e","datavalue":{"value":{"amount":"+0.8784065","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":"Q5935599$03A0B4B3-50AF-4617-8944-3A57651C5202","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b09f969d7a47514076abf123d45394241cdb38c","datavalue":{"value":{"entity-type":"item","numeric-id":3355252,"id":"Q3355252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39d921b0efc7cc7c81d2a43e6eaf5db6cff6b6ae","datavalue":{"value":{"amount":"+0.8783328","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":"Q5935599$B636EE70-466E-43BD-8C75-2F1FCACAEE70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03eec823f0a5a8ba5ccb9ebfa101c938b0259886","datavalue":{"value":{"entity-type":"item","numeric-id":4414511,"id":"Q4414511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8701ea6c48db8beaf5cacd49c5d7ae687ab2c5a","datavalue":{"value":{"amount":"+0.878256","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":"Q5935599$CA1E2C03-1A18-4126-AC9D-D18B043A6CB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb489f3e2e8e83ec79b6d08a8439ec8da809630d","datavalue":{"value":{"entity-type":"item","numeric-id":5946757,"id":"Q5946757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0132997b5c95d1dc6df39c5cc0a514a0ed767485","datavalue":{"value":{"amount":"+0.8782014","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":"Q5935599$B58678D7-7F1A-4202-A005-A8B8762F0378","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a4c4d64f42ab35066478657c035eb769d16e415","datavalue":{"value":{"entity-type":"item","numeric-id":987672,"id":"Q987672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"733c5fe3fe08ef62388d511cb4a1030123d7d35c","datavalue":{"value":{"amount":"+0.8748425","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":"Q5935599$D7A98CA8-297A-41F8-86ED-8EF9532F51B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e902a13e9860733107a8c6b34e8edc89a09c00a2","datavalue":{"value":{"entity-type":"item","numeric-id":4642251,"id":"Q4642251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed51792983633a7e280f2131c6598521005ec144","datavalue":{"value":{"amount":"+0.8747664","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":"Q5935599$6EE4B774-11A2-4969-B2E8-16E48CC37642","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5935599","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5935599"}}}}}