Graphs or networks are a natural way to analyze inter-related set of entities. When these entities are associated with a diverse number of features, each denoting a specific perspective, then the representation can be simplified by forming a network of layers (one for each feature) or multiplexes. Vertices with high centrality values in the multiplexes represent the most influential vertices. However, detecting central entities in multiplexes for different combinations of features becomes computationally expensive, as the number of layers increases. In this paper, we address the task of efficiently identifying high centrality vertices for any conjunctive (AND) combination of features (as represented by multiplex layers.) We propose efficient heuristics that only use results from individual layers to identify high degree and high closeness centrality vertices. Our approaches, when applied to real-world, multi-featured datasets such as IMDb and traffic accidents, show that we can identify the high centrality vertices with an average accuracy of more than 70-80% while reducing the overall computational time by at least 30%.