Computational Complexity of Cycle Discrepancy

L. ASLAM, S. SARWAR, M. M. YOUSAF, S. W. JAFFRY

Abstract


The irregularities or the deviations from the state of absolute uniformity are the core focus of the area of discrepancy theory. Cycle discrepancy is about the quantification of the least possible deviation of bi-labeling of graph vertices from an ideal bi-labeling which divides each cycle of a graph in two equal parts. This paper shows that it is NP-hard to compute the cycle discrepancy of a given graph. A polynomial time reduction of Hamiltonian problem to the problem of computing cycle discrepancy is used to establish this result.


Full Text:

PDF

Refbacks

  • There are currently no refbacks.


Copyright (c) 2018 Sindh University Research Journal - SURJ (Science Series)

 Copyright © University of Sindh, Jamshoro. 2017 All Rights Reserved.
Printing and Publication by: Sindh University Press.