Computational Complexity of Cycle Discrepancy
SINDH UNIVERSITY RESEARCH JOURNAL -SCIENCE SERIES · 2019
DOI: 10.26692/sujo/2018.09.0086 ↗Kurz gefasst
Fachartikel in der Zeitschrift SINDH UNIVERSITY RESEARCH JOURNAL -SCIENCE SERIES, 2019. Verfasst von L. ASLAM und 3 weiteren Autor:innen.
Abstract (Originalsprache)
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.
Zitieren
APA
ASLAM, L., SARWAR, S., YOUSAF, M. M., & JAFFRY, S. W. (2019). Computational Complexity of Cycle Discrepancy. SINDH UNIVERSITY RESEARCH JOURNAL -SCIENCE SERIES. https://doi.org/10.26692/sujo/2018.09.0086
Vancouver
ASLAM L, SARWAR S, YOUSAF MM, JAFFRY SW. Computational Complexity of Cycle Discrepancy. SINDH UNIVERSITY RESEARCH JOURNAL -SCIENCE SERIES. 2019. doi:10.26692/sujo/2018.09.0086
BibTeX
@article{ASLAM2019,
author = {ASLAM, L. and SARWAR, S. and YOUSAF, M. M. and JAFFRY, S. W.},
title = {Computational Complexity of Cycle Discrepancy},
journal = {SINDH UNIVERSITY RESEARCH JOURNAL -SCIENCE SERIES},
year = {2019},
doi = {10.26692/sujo/2018.09.0086}
}
EUVIMED