Advertisement
Published in:
2018 | OriginalPaper | Chapter
Realizability of Graph Specifications: Characterizations and Algorithms
Authors : Amotz Bar-Noy, Keerti Choudhary, David Peleg, Dror Rawitz
Published in: Structural Information and Communication Complexity
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
The study of graphs and networks often involves studying various parameters of the graph vertices, capturing different aspects of the graph structure, such as the vertex degrees or the distances between the vertices. Given an n-vertex graph G and a parameter of interest f, one may associate with G a vector \(\mathcal{F}(G)=\langle f_1,\ldots ,f_n\rangle \) giving the value of f for each vertex. This vector can be thought of as the f-profile of the graph. This paper concerns the dual problem, where given an n-entry f-specification vector \(F=\langle f_1,\ldots ,f_n\rangle \), we need to decide whether it is possible to find a graph G realizing this specification, namely, whose f-profile \(\mathcal{F}(G)\) conforms to \(F\). The paper introduces the notion of graph realiziations and illustrates a number of example problems related to finding graph realiziations for given specifications.