{"entities":{"Q1201812":{"pageid":1212561,"ns":120,"title":"Item:Q1201812","lastrevid":47119795,"modified":"2025-12-31T18:06:27Z","type":"item","id":"Q1201812","labels":{"en":{"language":"en","value":"\\(P_ 4\\)-trees and substitution decomposition"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 98504"}},"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":"Q1201812$37D0A89A-56F4-44F8-B5E7-105110C171E9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ebc5853a94088f8e0cc4f0bd096300c4089b9ddd","datavalue":{"value":{"text":"\\(P_ 4\\)-trees and substitution decomposition","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1201812$83F8E5FF-EB66-48A8-89C7-2CF6BCC0C708","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"553386717d590c86ecd0c836547a88132e160998","datavalue":{"value":"0758.68036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201812$3FF21F12-CB3D-495A-B76A-AA280257FCF7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2e66246d21e3ea543cbc4c0a0dbd1bb4d79af7dc","datavalue":{"value":"10.1016/0166-218X(92)90180-I","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201812$78B5B061-B3BB-446B-AA77-D9F07976F9F0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$C7FC3F6E-20F1-4DEF-92C1-7498844C6670","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b0879f591850b4f9f14b2c481d3e08995aa22089","datavalue":{"value":{"time":"+1993-01-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1201812$6A7753F2-6521-4217-B0FC-15115F30A7EF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7c2d60f3388479f157ccb34bb19f88cab9c4232a","datavalue":{"value":"Cotrees for cographs (\\(P_ 4\\)-free graphs) are generalized to \\(P_ 4\\)- trees, which can be used to give the modular decomposition of the graph. A vertex addition algorithm is given to construct the \\(P_ 4\\)-tree of an \\(n\\)-vertex \\(m\\)-edge graph in \\(O(n+m)\\) time. A second algorithm is then given to produce the modular decomposition of the graph in almost linear time. A very clear summary of the applications of modular decomposition is included.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201812$E50128F8-3490-47B0-A849-476C9ADC500F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8ba0869bc4942831c8669ed75022f72a56f93072","datavalue":{"value":{"entity-type":"item","numeric-id":168193,"id":"Q168193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$42D3BC6E-CFF1-4C7E-973E-B40A82CC4A5A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201812$8645BCA4-6704-4270-9DC1-65ECD8028DB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201812$100FECF1-7959-42BF-8B5F-7D5DC23B5285","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201812$38765C6B-3A8C-46C9-A03B-4A7F5724A4A4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4a344971eb8958d45f62f5354a3efc7dc28cf42c","datavalue":{"value":"98504","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201812$BB09D20B-72E5-4452-9753-AB017C349444","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"41e59eefb9bd4cf723e9df4a9fcbd56f44cddfa0","datavalue":{"value":"substitution decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201812$D5D82608-D8B8-4178-A93D-A34EBE6F9D45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8662a91bee3e0b1acb28fa6a98a0c55e724b5718","datavalue":{"value":"cotrees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201812$C51BD70C-6AA1-4C49-8F11-20DA6542C88B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df7fe14c7b38fce52b1c24ba095651ec0120be54","datavalue":{"value":"cographs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201812$329EAAF7-A845-467A-B37F-24DD588B2410","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1adb1579ecb6bb9aaca40d9ceb17f3584d731fa","datavalue":{"value":"modular decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201812$D3443A36-3A98-41CD-A5C0-BCCEEF498B1E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ef8392e01c11e85b032ddf62d87088b822bd19a","datavalue":{"value":{"entity-type":"item","numeric-id":344852,"id":"Q344852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$CB291896-F660-4B1A-97E6-2089557DA3C8","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":"Q1201812$8B80043C-1A62-42FD-B089-D3C12545201E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"13a13bf5ea222488a462597a035d6c581000a87a","datavalue":{"value":{"entity-type":"item","numeric-id":3665151,"id":"Q3665151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$222A8258-223E-4A7F-9149-D5159CBF9F20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d36f3d9c904ab8c45697085bc58a78dadcd15ec","datavalue":{"value":{"entity-type":"item","numeric-id":1160636,"id":"Q1160636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$001D7F88-A59A-4E9F-874B-F0DDCEBA7639","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7df60897b7f36fcb755315945b431813c52a78e4","datavalue":{"value":{"entity-type":"item","numeric-id":3910010,"id":"Q3910010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$532C734C-5C9C-467B-9AA2-97FCF45BC885","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecb8b11e8657ed748318814c5aac440e71814ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1153105,"id":"Q1153105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$18575A8D-B34B-4EA0-9D72-FC4358521785","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3edc2fe01664e7ae5dbedc60a81011b311142a1b","datavalue":{"value":{"entity-type":"item","numeric-id":3694709,"id":"Q3694709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$5070B2FF-D96B-468D-8311-826213ACFECF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d4d8a1c3628c934e726723cf3f6edf3c81d6fd1","datavalue":{"value":{"entity-type":"item","numeric-id":3960725,"id":"Q3960725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$539159C0-9E89-4EBF-89A1-193A4914FFD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8539d1fcf3cff5fbb08dd6973662b887ad57892","datavalue":{"value":{"entity-type":"item","numeric-id":5534028,"id":"Q5534028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$4FFE78C3-3C04-4BBD-BE86-B29FF4805749","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c998f37ea2af5fb09fab159d72a9dd7f47c2d7d1","datavalue":{"value":{"entity-type":"item","numeric-id":1235707,"id":"Q1235707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$BA99C494-CED2-493E-AD5A-732B4333508B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$7A8F5491-F2C5-4675-A3EB-32E751698838","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c63cd5f29576c98d890ea65d91adf5381d9c85d0","datavalue":{"value":{"entity-type":"item","numeric-id":1142232,"id":"Q1142232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$4AAF679D-4AF5-4668-BAE4-CDBB3E9F8FAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6565fcfa0421e1c14ba4c0bc259279332673885","datavalue":{"value":{"entity-type":"item","numeric-id":5598258,"id":"Q5598258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$6FAB3B27-3042-48C0-8EBC-6D1EB37B2A0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23fe0b762ba59e21ab429837d2d6d47161fd5d6c","datavalue":{"value":{"entity-type":"item","numeric-id":4151722,"id":"Q4151722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$17FCD276-050A-416B-8E23-E8FBBBDA5D97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"886ba032e540aea708d21bd27fbc92799a765ca4","datavalue":{"value":{"entity-type":"item","numeric-id":3686754,"id":"Q3686754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$D061C4DA-0D05-4654-B64E-4ADB05A68056","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec7cbae1c1118a2e1a65c80b733f652572b93c30","datavalue":{"value":{"entity-type":"item","numeric-id":4918387,"id":"Q4918387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$C9E9519F-4E3F-45ED-B72A-108F3901BB63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93a0021bb8eb537cd0811e93c7490e7e9ba98e6d","datavalue":{"value":{"entity-type":"item","numeric-id":3683903,"id":"Q3683903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$10E07DE5-1B72-497E-9E11-B52E35D62199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4ea2af1a8c93ceb977d8f389518ef463650adb3","datavalue":{"value":{"entity-type":"item","numeric-id":3823808,"id":"Q3823808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$4F50634B-F81F-498C-99D4-83FC55DC8DCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1ca25f33b598e553490e1213a9228decd88e954","datavalue":{"value":{"entity-type":"item","numeric-id":1130879,"id":"Q1130879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$5A58204D-B14A-4D28-9F21-50EA03164AA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e726b4bb0f5fe61b2034806faf70fe56dddfd25","datavalue":{"value":{"entity-type":"item","numeric-id":2545312,"id":"Q2545312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$B9637E1D-2065-412C-8C2F-FDBD8F18C848","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71aa46ea90d9e4629fd91e8aa5caba373a1bc71c","datavalue":{"value":{"entity-type":"item","numeric-id":4060706,"id":"Q4060706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$44318D56-2C14-4E5F-A2B5-51A5834AC526","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"636aef2901b7344bc99281d55b872e14ab1969f3","datavalue":{"value":{"entity-type":"item","numeric-id":3750504,"id":"Q3750504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$718E00DA-B55D-4061-819F-715810C03C75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"565e1c631f28f5626e28b4b72f070c887ee0b094","datavalue":{"value":{"entity-type":"item","numeric-id":3685215,"id":"Q3685215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$AA7DE66F-FE18-4A5C-ACE8-BF74E70C69E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"706d11973bdd8ea3d95f9ef55f4a226845d2fcc6","datavalue":{"value":{"entity-type":"item","numeric-id":3670598,"id":"Q3670598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$739155FC-3F18-4E70-A831-D15CE8495918","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9b4c2bc9c2f01a8608a2c200aa0923fb77f3748","datavalue":{"value":{"entity-type":"item","numeric-id":3929382,"id":"Q3929382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$F446E14F-BC42-48CC-99DD-21B25A53CE4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d932d2dd9959d01e52a083bc9b3ddf17f04db94","datavalue":{"value":{"entity-type":"item","numeric-id":1092072,"id":"Q1092072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$D38648C9-648A-4C8D-A3C7-0C11E8D83D10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d6ac11073d1feae5d3b5ea3b3fb57bb14591823","datavalue":{"value":{"entity-type":"item","numeric-id":1394240,"id":"Q1394240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$A97785D5-F40F-4989-ABFA-6C1F3B402CC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"932383d1ac997ed208ef47dcb574b592efaf75b3","datavalue":{"value":{"entity-type":"item","numeric-id":4065031,"id":"Q4065031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201812$8082C9D1-EF67-4D38-9A96-A94440EC21E6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea4281f28128764d50d8ce861e1a681dab131c79","datavalue":{"value":{"entity-type":"item","numeric-id":3676177,"id":"Q3676177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c8a32cd44c1d648d61c3bc99d74b15edb616fbf","datavalue":{"value":{"amount":"+0.8092807531356812","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":"Q1201812$9C9EB225-3740-4D62-BDF9-A5A08734CA09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32ec3dfb75a83121149248751be2001ccf6af098","datavalue":{"value":{"entity-type":"item","numeric-id":1183332,"id":"Q1183332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3133d4478f84434a89ea023196f2a36d6a04bcc0","datavalue":{"value":{"amount":"+0.8034148216247559","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":"Q1201812$4C760CB3-5A5F-48A7-920F-6C36C58D2855","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6bac441dd73cb7f7fd3eae0f7634f086cb0ab231","datavalue":{"value":{"entity-type":"item","numeric-id":4954442,"id":"Q4954442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0979c6fda74e63f218e8ad49bc81f170dfe76151","datavalue":{"value":{"amount":"+0.801781177520752","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":"Q1201812$DABA684E-9291-431C-ACC7-D026F1037D80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79bf5f6ce8eb9a3eb93353cbb1f75e605fa67e63","datavalue":{"value":{"entity-type":"item","numeric-id":3694709,"id":"Q3694709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d531d3de6162089d03a69b1971bdc34a511d9231","datavalue":{"value":{"amount":"+0.7960116267204285","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":"Q1201812$E82A0C8A-C883-4422-BB82-D5B2E9FF0315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8fd0e812e73fe49e4d8cb2fb115aeb867b041894","datavalue":{"value":{"entity-type":"item","numeric-id":1764804,"id":"Q1764804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d084bbc962d55e86ae9b1c5aee6a2223ee7c6967","datavalue":{"value":{"amount":"+0.7941488027572632","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":"Q1201812$E2A06D9C-D884-42EB-8B80-92CB08C4F489","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1201812","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1201812"}}}}}