{"entities":{"Q1108808":{"pageid":1119557,"ns":120,"title":"Item:Q1108808","lastrevid":66735036,"modified":"2026-04-12T12:31:00Z","type":"item","id":"Q1108808","labels":{"en":{"language":"en","value":"A parallelizable lexicographically first maximal edge-induced subgraph problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4068315"}},"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":"Q1108808$1512F2F5-81BB-4176-BA30-21EBA7B06779","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"aa567e1e09ab417d2e05ae981a58207fdd4aecf7","datavalue":{"value":{"text":"A parallelizable lexicographically first maximal edge-induced subgraph problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1108808$0C2E9ABF-0A69-4EB2-A754-07916772FBA8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"285af03f8b69ac5473c783166452b7cf92eebbc1","datavalue":{"value":"0654.68085","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108808$5E0D22D4-CC02-47E5-B39C-4609FEE2F164","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b7259164ade17443c6c44ebc1b3a61ebf6cffb8a","datavalue":{"value":"10.1016/0020-0190(88)90095-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108808$B14AAAC6-C35C-4679-B922-9C29A79725EC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c72921619bb1683825427c57b2aba25da8a8b109","datavalue":{"value":{"entity-type":"item","numeric-id":610146,"id":"Q610146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108808$549B70AF-86F3-49A5-9E24-545775B1244F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108808$E69A2488-06A4-48AC-95F0-E98D4799D313","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1108808$C0CCAC48-476D-4B4D-9872-5CD73A6A04FB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"86f7febe8f1b3f3199d4f65e1bc8bd74695a3841","datavalue":{"value":"The lexicographically first maximal 3-cycle free edge-induced subgraph problem is in \\(NC^ 2\\) when the instances are graphs without any subgraphs homeomorphic to \\(K_ 4\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108808$E57B83A8-3E97-4BEB-91C0-4D4A8BDC222B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108808$CA979C98-DDB0-4CD7-91A8-EA4377CD9118","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108808$6D5567DA-DDF4-4B11-9502-D3783F501FE7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"deec9201c10cd5b6970ef52acd4a855001afd71b","datavalue":{"value":"4068315","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108808$886B3394-FE7E-4DBF-955D-F85A2E053AFB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cad5bc9a485aa46ea3c3246e380097d0d8214c78","datavalue":{"value":"NC","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108808$CA414C15-ACEC-434B-967C-314FAA4A0C42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3c7ccf0017a583893b6cabee4e3a3e85178f360e","datavalue":{"value":"maximal subgraph problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108808$9BE75920-E468-494B-801F-72E66ED9C938","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed35a9fa19458304c0b74dd4e65451fe88c0a624","datavalue":{"value":"triangle-free","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108808$CACDCB1B-507B-4F97-952E-0855351B0EAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f46cb417b22e2492ff05b910c788c087363d7f23","datavalue":{"value":"outerplanar","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108808$2A583B5B-6943-4CC3-9D2E-61EA18008E13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6db291ad9f7ea62aa36d41bcd1bf31a1f6a916e8","datavalue":{"value":"3-cycle free edge-induced subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108808$100746DC-37E8-497C-8D7F-69A9E8F60EB4","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":"Q1108808$5FA104C1-F7D8-4248-8355-112A16FF0D1A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c30cc2e854d80bf53d8e1352199ec6ec7180a963","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90095-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1108808$3AF55685-F09C-4036-BFFD-12699334AE09","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d10e01a6d8f5c7d596df7c2324dfe287a1299beb","datavalue":{"value":"W2078777386","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108808$962F3E3E-757B-4693-BC5C-D9A2EBD30D0F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"14c31d1cbbb3f608df266c0768589c5cc798344d","datavalue":{"value":{"entity-type":"item","numeric-id":5545841,"id":"Q5545841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108808$919A24F6-BB9E-4EB0-973C-431A4CCD1023","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b90df03a170fcc85d9f6d5af38c0866a51f22b3f","datavalue":{"value":{"entity-type":"item","numeric-id":3694688,"id":"Q3694688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108808$134C51E1-6BA7-4EFB-8B3F-89A4BE04D5CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ef47a738eba0b33c21d022be5c49b064d45ce78","datavalue":{"value":{"entity-type":"item","numeric-id":3783600,"id":"Q3783600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108808$62B50807-4C56-4B22-9DBD-566AD87AB2C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0751213ac1721d4b7bcbd9ddb031d0ca4971a705","datavalue":{"value":{"entity-type":"item","numeric-id":1145502,"id":"Q1145502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108808$0C22C68D-3779-4822-8A51-3599402B84D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6dc1aefb41876da5771367e0b82d23ae6d455be5","datavalue":{"value":{"entity-type":"item","numeric-id":3692896,"id":"Q3692896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108808$EF518190-8239-4364-9000-BB8939E9C0E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f450486e6dd81b9bc183a0057d83ff04fd2d4632","datavalue":{"value":{"entity-type":"item","numeric-id":3316595,"id":"Q3316595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108808$5A9CE11E-F71D-4C29-8BE8-3280D6B7565D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad9cfae9fc9d02b6b7648a5f38f2a07226c5c18d","datavalue":{"value":{"entity-type":"item","numeric-id":3311677,"id":"Q3311677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108808$54FAA941-1C06-46D1-AD33-7582E7DED2FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22abc66855f38f366ed306bc6351e5f652676f21","datavalue":{"value":{"entity-type":"item","numeric-id":3785974,"id":"Q3785974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108808$06E8487E-905F-4674-B9B1-9959817EDC82","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A parallelizable lexicographically first maximal edge-induced subgraph problem","badges":[]}}}}}