En kantfärgad riktad graf är observerbar om ett medel som rör sig längs dess kanter från nod till nod kan bestämma sin position i grafen efter en tillräckligt lång observation av kantfärgerna, och utan att få tillgång till någon information om de korsade noderna. När agenten endast då och då kan bestämma sin position, sägs grafen vara delvis observerbar. Observationer i diagram är önskvärda i situationer där autonoma agenter rör sig på ett nätverk och de vill lokalisera sig själva med begränsad information. I denna uppsats karakteriserar vi helt observerbara och delvis observerbara grafer och visar hur dessa begrepp relaterar till andra begrepp i litteraturen. Baserat på dessa karakteriseringar tillhandahåller vi polynomiska tidsalgoritmer för att bestämma observerbarhet, för att bestämma partiell observerbarhet, och för att beräkna det minimala antal observationer som krävs för att hitta positionen av en agent. I synnerhet visar vi att i värsta fall ökar detta minimala antal observationer kvadratiskt med antalet noder i grafen. Vi betraktar sedan den svårare frågan om att tilldela färger till en graf för att göra den observerbar och vi bevisar att två olika versioner av detta problem är NP-komplett. .be (R.M. Jungers), vincent.blondel@uclouvain.be (V.D. Blondel). 1 Egenskapen att vara observerbar är en egenskap hos riktade grafer som har sina kanter färgade. För enkelhetens skull kommer vi att tala i vad som följer om observerbara grafer snarare än observerbara kantfärgade riktade grafer. 0166-218X/$ -se huvudfrågan
Grafen observerbarhet problem infördes av Jungers och Blodel REF, som visar att vissa variationer av problemet är NP-komplett i allmänna riktade grafer.
Observable graphs
{'venue': 'Discret. Appl. Math.', 'journal': 'Discret. Appl. Math.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}