Vi relaterar två begrepp i grafteori och algoritmisk komplexitet, nämligen söknummer och vertex separation av en graf. Låt s (G ) betecknar söknumret och vs (G ) betecknar vertex separation av en ansluten, oriktad graf G. Vi visar att vs (G ) ≤ s (G ) ≤ vs (G ) + 2 och vi ger en enkel Vi karakteriserar de träd som har en given vertex separation och beskriva de minsta sådana träd. Vi noterar också att det finns träd för vilka skillnaden mellan söknummer och vertex separation verkligen är 2. Vi ger algoritmer som, för alla träd T, beräkna vs (T ) i linjär tid och beräkna en optimal layout med avseende på vertex separation i tid O (n log n ). Vertex separation har tidigare varit relaterat till progressiv svart/vit sten efterfrågan och har visat sig vara identisk med en variant av söknummer, nod söknummer, och till sökväg bredd, som har relaterats direkt till gate matris layout kostnad. Alla dessa egenskaper är kända för att vara beräkningsmässigt intractable. För fast k, en O (n log 2 n ) algoritm är känd som avgör om en graf har sökväg bredd som mest k.
Förhållanden mellan söknummer och vertex separation är etablerade i REF och metoder för att beräkna vertex-separation layout problem visades vara tillämpliga för att beräkna strategier i O(n log n) och bestämma söknumret i O(n) för vissa fall av problemet.
The Vertex Separation and Search Number of a Graph
{'venue': 'Inf. Comput.', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}