{"entities":{"Q1736715":{"pageid":1747456,"ns":120,"title":"Item:Q1736715","lastrevid":57590913,"modified":"2026-03-31T13:01:22Z","type":"item","id":"Q1736715","labels":{"en":{"language":"en","value":"Finding supported paths in heterogeneous networks"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042287"}},"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":"Q1736715$5D40F0DF-2F5B-433F-944D-B3ADF6494793","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8cb2424354d2c1c643d00a1f3cf273f8644bca3a","datavalue":{"value":{"text":"Finding supported paths in heterogeneous networks","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736715$21ED2411-434F-4325-A218-A76B51075185","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6b6d9c5a239ba812051817be8bcf205b521a708a","datavalue":{"value":"1461.68151","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736715$60C51A1C-406D-4B98-8B4B-BA623EB4D6CD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"12b5ccded8b356b7268dd85ef762243ca8396c0e","datavalue":{"value":{"entity-type":"item","numeric-id":214959,"id":"Q214959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736715$C18174D0-FB33-4B00-861B-3F0473DE3646","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"29059e2f09a1df9f3661c0edc8342a0d775ce5bc","datavalue":{"value":{"entity-type":"item","numeric-id":329036,"id":"Q329036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736715$E11CD65C-E5C8-4B7C-AF73-77063DBC080E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b6455bfd6e0a885a570c4a9fb9b8f233d001b8af","datavalue":{"value":{"entity-type":"item","numeric-id":479024,"id":"Q479024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736715$ACD3759C-86C9-4C98-9319-9F8AA1D013DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3d173afbda7d364ee20fa0af1c6602b56374da2","datavalue":{"value":{"entity-type":"item","numeric-id":187141,"id":"Q187141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736715$EE56433A-932B-4C86-ABF3-14464A2B8DB8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736715$566F764D-7E6E-4E9A-95D9-93A8C647D71C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1736715$74A2F022-C93A-4D30-962A-169A3582CBE8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"60d035044eca2d111ca7789ce7d040308e3055f6","datavalue":{"value":"Summary: Subnetwork mining is an essential issue in the analysis of biological, social and communication networks. Recent applications require the simultaneous mining of several networks on the same or a similar vertex set. That is, one searches for subnetworks fulfilling different properties in each input network. We study the case that the input consists of a directed graph \\(D\\) and an undirected graph \\(G\\) on the same vertex set, and the sought pattern is a path \\(P\\) in \\(D\\) whose vertex set induces a connected subgraph of \\(G\\). In this context, three concrete problems arise, depending on whether the existence of \\(P\\) is questioned or whether the length of \\(P\\) is to be optimized: in that case, one can search for a longest path or (maybe less intuitively) a shortest one. These problems have immediate applications in biological networks and predictable applications in social, information and communication networks. We study the classic and parameterized complexity of the problem, thus identifying polynomial and NP-complete cases, as well as fixed-parameter tractable and W[1]-hard cases. We also propose two enumeration algorithms that we evaluate on synthetic and biological data.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736715$53F80627-9BEA-4CFC-B841-BDC139E3499F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736715$0A7D070E-0618-4163-94F1-A243A85BC675","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736715$DEFE3AA4-D659-4CEB-8702-7E0E3900997E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736715$94D36637-59E2-457B-9A34-596F9CD37AE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736715$05A8889A-4CFC-41B4-A2F9-F2FADBBE1617","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736715$37DB1797-F30B-4F1D-89B3-D3E5C21883FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"33dbd2fb5ca21d3b7512e0368d809229686ea08a","datavalue":{"value":"92C42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736715$8C0BD888-2EC6-43D9-BDC1-7874AB92DCF8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"aab1273b3bf005de85657ed627eff3bced4b0019","datavalue":{"value":"7042287","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736715$EFBD6525-18D0-4CD3-9A9D-51723000D4A6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99974e488eefe65e9a359b970a995a9b6d33d8e8","datavalue":{"value":"NP-hard problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736715$76DDC442-2D15-4067-AE9E-DB08C97DC320","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c2155b1f0f1b7934ea2f00e74be522bfbe52774","datavalue":{"value":"directed acyclic graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736715$73012679-994F-4E07-B95E-27749D1D2EE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e826d58a24639276484be95f2b31a438a61d3e6","datavalue":{"value":"longest path problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736715$FD7AB364-CB8F-47D9-884B-A7B5863ED9A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd7acf520a21d8e190f14ac449e5bdb2ea791d04","datavalue":{"value":"shortest path problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736715$2EA154B8-07CC-4612-9606-196F002775D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b66d56262899b054aaafb068ff7bbc66b1b08f6","datavalue":{"value":"protein interaction networks","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736715$74E0E744-B935-46AC-8359-ECE7F8B46239","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4444f0264930019b0217e805aa4883437153e263","datavalue":{"value":"metabolic networks","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736715$E03D5608-BA73-4CDC-B037-99E3035AE60A","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"9ead0ebf4d86b2c760c29a7e4fead2c30898a5ba","datavalue":{"value":{"entity-type":"item","numeric-id":41451,"id":"Q41451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736715$BA33DFFC-5DF1-4D83-8AE6-1294F5CE16B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"269a6fa6fb65715095a4f55319c87d31b71ec7c1","datavalue":{"value":{"entity-type":"item","numeric-id":27808,"id":"Q27808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736715$6C618C18-BFE9-41AB-8BDB-73F6012AE644","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":"Q1736715$81DF4A4E-AF10-4995-8BEE-AD4C2354034B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fd532f6e808032f0ff0cdfdc86158afdab017ece","datavalue":{"value":"https://doi.org/10.3390/a8040810","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736715$F1BC2A0C-BD49-427C-8201-2F4AEA87F779","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"aeba389c47f688ac9cf672936cd713ea27f94ec8","datavalue":{"value":"W1885685411","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736715$7F953DB1-0C4E-44AC-8F28-7741821C36D6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae35b42269b65df7a1c59338bf97c0ea301c5c81","datavalue":{"value":{"entity-type":"item","numeric-id":2488567,"id":"Q2488567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736715$B610FD7C-E1BC-409B-BBCE-8A7A431DB1EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e1357b15aa0895d858d392a7ff419092326aafa","datavalue":{"value":{"entity-type":"item","numeric-id":5710169,"id":"Q5710169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736715$990B5100-E56A-451A-997D-6DC0F5D553D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c2045a7ec56e01f15e3eae4db248ef2b73a81db","datavalue":{"value":{"entity-type":"item","numeric-id":1132111,"id":"Q1132111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736715$38116FA8-B4E5-465A-86A7-201930778A7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736715$14537F42-C2F9-4C49-BDBA-0ED218C9BBFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5dbb60cde7f55c02cccf62f929b356800cce32f3","datavalue":{"value":{"entity-type":"item","numeric-id":1001898,"id":"Q1001898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736715$CFD38FA5-93D9-4422-A857-7DB9FE71E681","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2713516d5fb030de132a1e00919d35b186780cfc","datavalue":{"value":{"entity-type":"item","numeric-id":2354725,"id":"Q2354725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736715$1DF0ECCA-6BCA-446A-A416-403BE66BD15F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba453736f5070f55cd4d267ba0cf61a80c0cfc6e","datavalue":{"value":{"entity-type":"item","numeric-id":3292043,"id":"Q3292043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736715$D11284E1-B89E-4165-BD65-3386130A9586","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cbad4944f17afff471966f84ddba81383864ae6","datavalue":{"value":{"entity-type":"item","numeric-id":3292045,"id":"Q3292045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736715$C0747CDF-8962-4F47-8A48-9C5042581289","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c425911d158eead98c059d835fb23fcf99a97196","datavalue":{"value":{"entity-type":"item","numeric-id":5199156,"id":"Q5199156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736715$2AEBC951-0A48-43B2-BCAC-17655D73688D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"13f8f6966da45d28c77d80a90bf710039ec86fd3","datavalue":{"value":"10.3390/A8040810","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736715$CD46D799-BE5A-4116-A1A5-ED41A4B5DFFE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e293bcc545638867980f3d46137e2e227960c82","datavalue":{"value":{"entity-type":"item","numeric-id":5199156,"id":"Q5199156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2ad9790f3d3bc5e9f45d6ef793e5d436eb42610","datavalue":{"value":{"amount":"+0.7622478604316711","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":"Q1736715$3FC2D35C-5AC5-446B-BAF7-5D4992B5BD33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29d791866e8b8e148987229f6ba340ecd331ec25","datavalue":{"value":{"entity-type":"item","numeric-id":995774,"id":"Q995774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4d6616a341fd780db4e9dc8df45c3b784a221a8","datavalue":{"value":{"amount":"+0.740403413772583","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":"Q1736715$03132D66-8CB9-4A7A-94AD-E1E539FB35A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c8f73a75edc0c718ea3ee61ce9c535b7264007e","datavalue":{"value":{"entity-type":"item","numeric-id":2669687,"id":"Q2669687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9bee720a1fd877ab85cfff313e679a8bd147ced3","datavalue":{"value":{"amount":"+0.7265480160713196","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":"Q1736715$5047F9DC-66E9-462E-9357-209A74CEF4A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"211f958236f3d4820635d597de2584a793227e6c","datavalue":{"value":{"entity-type":"item","numeric-id":533412,"id":"Q533412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26e22a2b4eea8f44ac7119df1769bc3a6b534e4a","datavalue":{"value":{"amount":"+0.7069402933120728","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":"Q1736715$B25D68E1-52D4-4E05-BE92-CEE398A4B6F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c85dad4fc06b1629c08390cb0b03a945e2bbb097","datavalue":{"value":{"entity-type":"item","numeric-id":2435702,"id":"Q2435702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c27ae1c28c265bfa8f1c95713bce6b7860369b09","datavalue":{"value":{"amount":"+0.7011562585830688","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":"Q1736715$A4F79038-4CEF-4532-A357-A07DF13022FC","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736715$C8F34253-C6CE-40F6-84C5-8ED3BE14F51C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1736715","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1736715"}}}}}