{"entities":{"Q678111":{"pageid":679960,"ns":120,"title":"Item:Q678111","lastrevid":63652083,"modified":"2026-04-11T14:37:26Z","type":"item","id":"Q678111","labels":{"en":{"language":"en","value":"On the feedback vertex set problem for a planar graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1000218"}},"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":"Q678111$E0C078EA-865C-4192-BC29-960E64B38235","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"db8b1e89a6a7302b351e46bb2b7a98d67afb63ed","datavalue":{"value":{"text":"On the feedback vertex set problem for a planar graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q678111$E62F67F0-1C82-471A-BA9B-78D22F0B45CA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"124e40540f6596865a725702c3fa4555732f2e6a","datavalue":{"value":"0870.05067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q678111$0A51E1FD-D2F5-4300-9A6C-43455973AF49","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"544ab489081bb98243fde1a7db44edf9d8435fe7","datavalue":{"value":"10.1007/BF02684436","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q678111$F08F1146-B748-4BD3-BBAE-D3BFB57AE151","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8434c09ad605d5ff41043d66e1f75098ea8e945a","datavalue":{"value":{"entity-type":"item","numeric-id":269807,"id":"Q269807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678111$B39BCE6B-0B13-4845-8E64-DE7D24A7E254","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b79ece58f33b59758a066cb6b9ee149bab3a2c9a","datavalue":{"value":{"entity-type":"item","numeric-id":167642,"id":"Q167642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678111$738FC169-C983-48EC-887D-41ACBFE2A4EF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8eb1335ea3ff8239be65e16ffb01fc1c1358604b","datavalue":{"value":{"time":"+1997-09-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q678111$BD64CADF-2D7A-494C-9612-28AFAEDBB2D8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e2732b8208c6a2c4d6f889818455c830443b9594","datavalue":{"value":"If a directed graph has cycles, we can remove some nodes so that the remaining graph becomes acyclic. Such a set of nodes is called a feedback vertex set. These nodes could form the set of indices involved in the Schur complement problem. The paper presents an algorithm for solving the feedback vertex set problem for planar digraphs. In particular, planar digraphs with a certain additional condition are considered as they arise from solving systems of linear equations obtained from convection-dominated flow problems. The proposed algorithm requires a computational work linear in the size of the digraph. As a side product, the algorithm for determining the feedback vertex set produces a disjoint decomposition of the digraph into subsets (concentric cycles) mainly consisting of one cycle.","type":"string"},"datatype":"string"},"type":"statement","id":"Q678111$85F2FCC0-06DF-4429-B21C-06CE87A7357B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"99fea3d876487c7181e0dff689e3c55a44323330","datavalue":{"value":{"entity-type":"item","numeric-id":592071,"id":"Q592071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678111$C4626264-3578-43CA-B1FA-5ACE945C9BBC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q678111$F9832A0C-C6DF-4B61-9145-5BBADECBECCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q678111$267EA149-E2E6-49DC-BA2A-B0AD4559529F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q678111$13B71AB3-5F57-4D2A-81D9-1622A24663A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q678111$74B5DE89-3ECD-445C-8357-588A307C7CB3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5f44d1b9e5651ed63b55a88ceb803f9f5a0c1b3c","datavalue":{"value":"1000218","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q678111$E241AC1F-5E4E-42FE-925A-7EA881723290","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"298a551ef47c5b20057a4bfdb8bbc9e28d84ca03","datavalue":{"value":"acyclic digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q678111$E8DC7013-D4D6-49CF-B6C2-2CB35B2D554E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bc032c638ef20db48507160c3aa9ea979ad5af77","datavalue":{"value":"feedback vertex set problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q678111$7CB092CA-2220-4990-A71A-6BB7863A2C33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3dd931642384fb57a8dd805071ac40dd0c1a29c","datavalue":{"value":"planar digraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q678111$7BC6786B-A2A9-4D66-965B-F512DEE3E60D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q678111$489D903C-0BFD-447F-8149-20D15640B324","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"615f2a3773e3a9a3bad386a540fbc6c58cfa22ee","datavalue":{"value":"decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q678111$5A92CF1A-F584-4EE5-8BD1-2A243007A321","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"7969250d1b4b8741f381abee838b2df06cbfffc7","datavalue":{"value":{"entity-type":"item","numeric-id":24581,"id":"Q24581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678111$AD3168B9-7A23-4281-9B29-504D25460315","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":"Q678111$0BA0C5A2-8D3A-4651-B5BE-5C11641A760E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e70b95611eefa59c5b5b70d889b92f5b12b3ede","datavalue":{"value":{"entity-type":"item","numeric-id":3779759,"id":"Q3779759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678111$71F24407-3698-4052-BA60-9057ABE97261","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd3511304867316fbfb65d4b4f901bafb5160d19","datavalue":{"value":{"entity-type":"item","numeric-id":1100915,"id":"Q1100915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678111$4F9D8BA6-F7CE-472A-B55B-4E98D13718C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f63af9064749b9a8486a37a1bdf3c100f684f16","datavalue":{"value":{"entity-type":"item","numeric-id":3727300,"id":"Q3727300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678111$8D5D41A6-830F-427F-B91E-DD0D15448074","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c39ddc64d447213410e175be21a0cd5734e365b9","datavalue":{"value":{"entity-type":"item","numeric-id":4023463,"id":"Q4023463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678111$A4634185-6176-4B25-B872-FBBBE1C29BAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c73690c57a74c8c54466d0d5ac7db82e05a8a26","datavalue":{"value":{"entity-type":"item","numeric-id":3123963,"id":"Q3123963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678111$9EB69248-5B0F-4D0E-B598-49F5784CEFAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04872738d50af98253ccedc10191fd45f44520ef","datavalue":{"value":{"entity-type":"item","numeric-id":3680289,"id":"Q3680289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678111$B31E9D1B-0335-4513-84E3-86BFB3891CF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d59c907c83d22e052e6b614b84133edda79a4f9e","datavalue":{"value":{"entity-type":"item","numeric-id":4028105,"id":"Q4028105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678111$DBF8B365-D24E-4A76-A51A-D40FCDC471B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"475ff6b2a8da8552ce337e2218c8c961d541a278","datavalue":{"value":{"entity-type":"item","numeric-id":4002949,"id":"Q4002949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678111$1F730A36-C547-4AF6-A9FE-240AEA5AD35A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5e3044c8fb149dff163a0624df6ca5166dff24d","datavalue":{"value":{"entity-type":"item","numeric-id":4228344,"id":"Q4228344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678111$5D182159-39B9-47B1-A65B-0D91C9C62617","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"825214dcb3cfd1ac61e00a99e476d66f3ac054ca","datavalue":{"value":"https://doi.org/10.1007/bf02684436","type":"string"},"datatype":"url"},"type":"statement","id":"Q678111$414B0D94-DF31-406D-A889-010D4235D9D6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e6ca755437453dc1f7aa91a093b11a4c0e1eb8d3","datavalue":{"value":"W1557534265","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q678111$2B62CF24-130B-44D7-98F8-2807F22CB8A9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00d50d7bbc3c8944b38e4ca6b73d25b976856a39","datavalue":{"value":{"entity-type":"item","numeric-id":1936089,"id":"Q1936089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2268e3f27a1dba9754088b370b4502bec784cdba","datavalue":{"value":{"amount":"+0.7577126026153564","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":"Q678111$6ECA856C-F570-4F2A-B61A-DC432B615872","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09326fac0bc224a6ed118cc448076a2e16388acf","datavalue":{"value":{"entity-type":"item","numeric-id":1111395,"id":"Q1111395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f33c13245e372e0792854db9eada4604482a210","datavalue":{"value":{"amount":"+0.739769458770752","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":"Q678111$97096959-E58B-4474-9158-B3FB7F960D34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75d23af14f5fc32b39473f6c658ddcf94497fc7e","datavalue":{"value":{"entity-type":"item","numeric-id":5463673,"id":"Q5463673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31ca7a178aa8d85e2fbc2f15f94d84829da7269d","datavalue":{"value":{"amount":"+0.7365071177482605","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":"Q678111$F3E78820-6F91-421D-A78A-C02AB40C0232","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b44545934a1747185e6bce30296f265d99a5d06e","datavalue":{"value":{"entity-type":"item","numeric-id":4028105,"id":"Q4028105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"302715eb94b8b5ebc7fc10d72c84ba7a432c7343","datavalue":{"value":{"amount":"+0.7321059703826904","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":"Q678111$E06A386B-227E-4B80-9545-27F198035B77","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the feedback vertex set problem for a planar graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_feedback_vertex_set_problem_for_a_planar_graph"}}}}}