{"entities":{"Q686253":{"pageid":688102,"ns":120,"title":"Item:Q686253","lastrevid":63608706,"modified":"2026-04-11T14:19:39Z","type":"item","id":"Q686253","labels":{"en":{"language":"en","value":"The efficiency of AC graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 428108"}},"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":"Q686253$74FC115C-EEE7-4077-9775-0C9E0205AB71","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2af306d6b158557a69e61335cd086eb6c43a13e5","datavalue":{"value":{"text":"The efficiency of AC graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q686253$30D40D4E-B8B6-4D6D-AF63-2985C7CC8070","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4f1c91b6dc50104b1d3059dd4639e39451a0116d","datavalue":{"value":"0788.68106","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686253$F535B401-ACB5-4BFC-9B86-2FD858D8A95B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0add188214d1b297f0d7609c92aeab80307d5fb3","datavalue":{"value":"10.1016/0166-218X(93)90227-F","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686253$89E06603-7D33-4CAC-B594-1E505AD6F1FD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"65d67b068ce702e9f191ab309af2757aae1f0e94","datavalue":{"value":{"entity-type":"item","numeric-id":442252,"id":"Q442252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686253$0FFBB1F1-DAF0-4BE4-9E7E-9AB3F1343A99","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":"Q686253$26FD5329-437E-455C-9D66-90A753E6EF89","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9a56fa44f05f9c865c2049cda281119f7946a004","datavalue":{"value":{"time":"+1993-11-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q686253$7F59F6B9-5CAF-4009-AD98-84F62300EE7F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3b76baa8e978d6e2fd9a156ac9ab41b532a51973","datavalue":{"value":"If \\(G=(V,e)\\) is an undirected graph with a distinguished subset \\(R \\subset V\\), then a vertex \\(v \\in V \\backslash R\\) is said to be dominated by \\(s \\in R\\), if \\(v\\) and \\(s\\) are connected by an edge. The maximum efficiency \\(\\varepsilon(G)\\) is the maximum number of vertices in \\(V \\backslash R\\) over all subsets \\(R \\subset V\\) that are dominated by exactly one node in \\(R\\). Expanding a result of \\textit{P. J. Bernhard}, \\textit{S. T. Hedetniemi} and \\textit{D. P. Jacobs} [ibid. 44, 99-108 (1993; Zbl 0780.68097)], the present author constructs a linear time algorithm for computing \\(\\varepsilon(G)\\) when \\(G\\) is an \\(AC\\) graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q686253$ECDA0239-1873-4988-800E-58547A2A7365","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686253$74BDD01E-A691-49D6-99B2-2A942717D49F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686253$248FA33F-E3A1-4F4C-AFE0-610EFF1C600E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686253$7A04ED62-824E-4947-88B5-54C2C6CFBCFD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"39d6f9c50fac082de68363e48f60b5c18d5e0e42","datavalue":{"value":"428108","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686253$2C6B13EA-4841-46A3-91D6-283392A2ED2F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f808a39bc410c6328d7bf2834ecfc2c5b31d146a","datavalue":{"value":"dominated vertex","type":"string"},"datatype":"string"},"type":"statement","id":"Q686253$477B0563-3758-4509-8DDB-735E932CC463","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e87d84681bbfa053b3522d309931ec090a9aac8f","datavalue":{"value":"maximum efficiency","type":"string"},"datatype":"string"},"type":"statement","id":"Q686253$006A118E-4FF1-4601-9B8C-412C2A19D2B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2988c062ef3f857cb058703c51c9117a94301b66","datavalue":{"value":"\\(AC\\) graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q686253$0AB6F637-A216-4D07-B032-EE335418BDC4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c57cdea2f65d9d15ca88202ede1c912bc6bece45","datavalue":{"value":{"entity-type":"item","numeric-id":249432,"id":"Q249432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686253$9B1B0884-2207-41C2-995E-CCB9DCC299B7","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":"Q686253$C3032A1D-4E6F-4E43-B5C0-E76EA1CBF622","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"34c7614b43d84c8d8ed1d554726839fa2acc4220","datavalue":{"value":{"entity-type":"item","numeric-id":802632,"id":"Q802632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686253$AE07D5AE-6A5A-46CA-896B-44DD59952EED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"363ff11584f05fc1e09b24072601f1f08374c7ea","datavalue":{"value":{"entity-type":"item","numeric-id":686251,"id":"Q686251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686253$72118CDC-ED46-4560-AA41-3B64B8263B16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94845758189c4aa84a9888727d2fb672313da67c","datavalue":{"value":{"entity-type":"item","numeric-id":3218070,"id":"Q3218070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686253$F5A7AF77-347A-4CF3-811C-696F016337C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b6e2632de5f3bd87e868f7586da85ea3e9d4521","datavalue":{"value":{"entity-type":"item","numeric-id":3315441,"id":"Q3315441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686253$37E0F5DA-F624-40A1-818F-BFFE56B7594A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3498f0fc8e71871e139619a5769a0845109f90c6","datavalue":{"value":{"entity-type":"item","numeric-id":1168728,"id":"Q1168728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686253$AB0E55B1-F84D-438F-920D-5890DB7B0CAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c66319ecf0caff7d798a39de5750d2791e9e6c56","datavalue":{"value":{"entity-type":"item","numeric-id":3822197,"id":"Q3822197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686253$685E8F42-528D-4C99-99D1-1172A364CCCE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7fb490cd6bdb450e05e2e3baffbb5e04e1b281f4","datavalue":{"value":"https://doi.org/10.1016/0166-218x(93)90227-f","type":"string"},"datatype":"url"},"type":"statement","id":"Q686253$28CB31C0-91EF-49DF-90F3-F03A4EAEF767","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bfd8693bdab2be112a507056d7d4ccc1b07c432d","datavalue":{"value":"W1980302408","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686253$AFFE8B24-FC48-4D29-8B83-4820EBEE2AB7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"329baccc1792c1e244c42ca67c6e066dd67c006a","datavalue":{"value":{"entity-type":"item","numeric-id":686251,"id":"Q686251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5469fd43136c7a90e3f95d9d388ab7036834c88a","datavalue":{"value":{"amount":"+0.8137187957763672","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":"Q686253$5CF77181-4B3F-4837-8757-C543DC4F5D16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba7ed87c70dbb06196b7814444d7b083a22e7e33","datavalue":{"value":{"entity-type":"item","numeric-id":266040,"id":"Q266040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4436b7b99cc02f3ed9a026b090865b4633ca1414","datavalue":{"value":{"amount":"+0.8123825192451477","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":"Q686253$A3E9619D-663C-40CE-B676-3C76663059D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03f0c36b8f2dad8381f3a2e8315fbc9e7d0a5a65","datavalue":{"value":{"entity-type":"item","numeric-id":686252,"id":"Q686252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"362a4b5b03e659e88566081c35cc13106c7c7d4d","datavalue":{"value":{"amount":"+0.7956986427307129","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":"Q686253$59AFBE48-D480-49DE-A9AE-8842F850E152","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e63811d1167a36279b483b70e01ec6a2abe04392","datavalue":{"value":{"entity-type":"item","numeric-id":1313728,"id":"Q1313728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1d9c0129388aa3034c3bf110bc12d6e50f977ef","datavalue":{"value":{"amount":"+0.7870936393737793","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":"Q686253$1F5FB0EA-9EE6-473A-9577-9A0EAA70EF51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76616cf4ce89c1a8379bdb33f94eb8a141d09ae9","datavalue":{"value":{"entity-type":"item","numeric-id":3815323,"id":"Q3815323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39d4ad7b81c99d7c2c6ebddc416bfc0c7c82b017","datavalue":{"value":{"amount":"+0.7524300813674927","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":"Q686253$71576775-BC2E-4FB0-8783-CB79F2BD5AF7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The efficiency of AC graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_efficiency_of_AC_graphs"}}}}}