{"entities":{"Q1578423":{"pageid":1589163,"ns":120,"title":"Item:Q1578423","lastrevid":72236418,"modified":"2026-04-14T03:32:10Z","type":"item","id":"Q1578423","labels":{"en":{"language":"en","value":"Graph searching on some subclasses of chordal graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1496852"}},"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":"Q1578423$43462B71-CE83-4B5B-A9F9-5C1F61EE21D7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5e82e2caa372db4f7413a245230d7c4c9ff32c63","datavalue":{"value":{"text":"Graph searching on some subclasses of chordal graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1578423$441966ED-9E5C-4E9E-A008-97766DFBF822","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9993b108c6ff13e81946ef7e001a3daa2f3ee2cc","datavalue":{"value":"0955.05074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578423$58753AA8-39DA-42FC-908F-BAE2701A63F9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"68394fd7e8a253e114d6399606d47416a190b2d2","datavalue":{"value":{"entity-type":"item","numeric-id":1511313,"id":"Q1511313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578423$223DF783-C7AB-4A43-B9D7-0042D75785D3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578423$69D4ABCE-48E1-4035-9128-218F8B017154","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"329211073fdec0c3c9c3797c513efe095760b570","datavalue":{"value":{"time":"+2001-02-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":"Q1578423$A5DC2315-CF52-4CE9-94DB-3990A4710352","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5d207ad086d32ab5b592ecc4fc8de7c691a7b970","datavalue":{"value":"Graph searching is the problem of cleaning the edges of a graph by a minimum number of searchers. An edge is cleaned by having searchers on both endpoints at the same time (node search) or by moving a searcher along this edge (edge search). Lots of equivalent problems are known, for instance, one plus the pathwidth of a graph equals its node search number [\\textit{N. Robertson} and \\textit{P. D. Seymour}, J.\\ Comb.\\ Theory, Ser.\\ B 35, 39-61 (1983; Zbl 0521.05062)], and edge search number and cutwidth are identical for every graph of maximum degree three [\\textit{F. Makedon} and \\textit{I. H. Sudborough}, Discrete Appl.\\ Math.\\ 23, No.\\ 3, 243-265 (1989; Zbl 0715.05012)]. A starlike graph is a chordal graph obtained from a split graph by blowing up the vertices in the independent set to clique modules. Node search remains NP-complete for starlike graphs [see \\textit{J. Gustedt}, Discrete Appl.\\ Math.\\ 45, No.\\ 3, 233-248 (1993; Zbl 0798.68134)], but can be solved in time \\(O(mn^k)\\) on \\(k\\)-starlike graphs (all the clique modules have size \\(k\\)). Edge search is NP-complete for chordal graphs but is solvable in linear time on interval graphs, in time \\(O(mn^2)\\) on split graphs and in time \\(O(mn^k)\\) on \\(k\\)-starlike graphs for \\(k \\geq 2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578423$59576AC1-6292-42FF-8BB9-E1A04D099D94","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578423$A2122F09-001D-426C-AEDE-7F1BA2B671BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578423$84350DDF-7510-4498-920C-98E2E6133B95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578423$E791324C-5325-43C9-8B5E-E4F47F414A05","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3b4e846452afb70b3dac648d5631d46e8e60c137","datavalue":{"value":"1496852","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578423$5CAE17AF-D3A9-408A-BC93-BD8D5F2ED082","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b322c03f72bfbe9e7516683225803e7e94a5704f","datavalue":{"value":"graph searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578423$C22E322C-46F6-4B3B-A09B-7D808F7D02DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72f3d9a740504a84929b982c7d1753e3110a1a95","datavalue":{"value":"node search","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578423$3E940817-CAFA-452C-81B9-EAF8DA4ABA1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e739d269ae46d6c790c96977db15aa4a59122753","datavalue":{"value":"edge search","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578423$A253E0E1-0808-41B6-BB6B-82923A1DFDE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f9e02e0c2fc7aaa54a35c42fa1d5643f6e2753ad","datavalue":{"value":"star-like graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578423$24154517-07F3-4A70-ABFF-CF2CA0FC7836","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8364c4db3fffd0a014142e381813cb4f26f28ac","datavalue":{"value":"split graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578423$743BD0D9-D90E-4524-B394-F2CB631D5E4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a949c568749d2f4337e1772be827516d5211abc","datavalue":{"value":"interval graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578423$15043EBB-D158-4E76-B664-416B3C9FCDD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578423$C47A94A8-F7D6-4084-84F5-5ABD40EE60D7","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":"Q1578423$C08EFB56-3C78-4A6E-B800-F586211AFB4D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"938be41ace031d7474654b8738f191ffdd274f1a","datavalue":{"value":"https://doi.org/10.1007/s004530010026","type":"string"},"datatype":"url"},"type":"statement","id":"Q1578423$E7F20E86-366B-4722-A349-837EC1CB507C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"117c2a30f91ff7e07b38a26a377f74d284155784","datavalue":{"value":"W1983243209","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578423$9361B987-5BBB-453C-96D9-DB5B5976C45F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a940196fef36c03b370baec374c619219d94500e","datavalue":{"value":"10.1007/S004530010026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578423$78D88A4C-E510-42EC-B7A9-8F30E467552F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b41b70c3f268cc89ab30042224a9d0d3d8a723c","datavalue":{"value":{"entity-type":"item","numeric-id":4489244,"id":"Q4489244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5d8186100614a92a64e718c73bdaf6f0a0c9e24","datavalue":{"value":{"amount":"+0.8530986309051514","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":"Q1578423$46F1A97A-19BE-4C8A-B197-8D47B9DA9B48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad35d025e50a7ea58f86d2daee6161ba1b9f5c8e","datavalue":{"value":{"entity-type":"item","numeric-id":967304,"id":"Q967304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f347333e208f9c31548251a8da400ba67d95ebe","datavalue":{"value":{"amount":"+0.8175034523010254","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":"Q1578423$3977F8E5-FA60-413B-BDA3-DFD2CC6384E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c48f3489c5099c9ed94068a2cec2f79dffb55ac7","datavalue":{"value":{"entity-type":"item","numeric-id":2706178,"id":"Q2706178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8f30fe5dcb02586111a9483047fb9052c60168c","datavalue":{"value":{"amount":"+0.7807744741439819","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":"Q1578423$91B03E07-AAC9-4D55-ACDE-E6D937864EE8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Graph searching on some subclasses of chordal graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Graph_searching_on_some_subclasses_of_chordal_graphs"}}}}}