A P-complete graph partition problem

R. Sarnath; Xin He

doi:10.1016/0304-3975(90)90026-E

A P-complete graph partition problem

R. Sarnath
, Xin He

Department of Computer Science and Engineering

SUNY Buffalo

Research output: Contribution to journal › Article › peer-review

Abstract

The Different Than Majority Labelling (DTML) problem has a simple polynomial time sequential algorithm. The labelling given by this algorithm is called the Lexicographical First DTML. In this paper we show that the LF-DTML problem is P-complete. Furthermore, we show that even when restricted to planar graphs, the LF-DTML problem remains P-complete.

Original language	English
Pages (from-to)	343-351
Number of pages	9
Journal	Theoretical Computer Science
Volume	76
Issue number	2-3
DOIs	https://doi.org/10.1016/0304-3975(90)90026-E
State	Published - Nov 21 1990

Access to Document

10.1016/0304-3975(90)90026-E

Cite this

@article{3f5fe65992d84f51aaca7d3c270d515d,

title = "A P-complete graph partition problem",

abstract = "The Different Than Majority Labelling (DTML) problem has a simple polynomial time sequential algorithm. The labelling given by this algorithm is called the Lexicographical First DTML. In this paper we show that the LF-DTML problem is P-complete. Furthermore, we show that even when restricted to planar graphs, the LF-DTML problem remains P-complete.",

author = "R. Sarnath and Xin He",

year = "1990",

month = nov,

day = "21",

doi = "10.1016/0304-3975(90)90026-E",

language = "English",

volume = "76",

pages = "343--351",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "2-3",

}

TY - JOUR

T1 - A P-complete graph partition problem

AU - Sarnath, R.

AU - He, Xin

PY - 1990/11/21

Y1 - 1990/11/21

N2 - The Different Than Majority Labelling (DTML) problem has a simple polynomial time sequential algorithm. The labelling given by this algorithm is called the Lexicographical First DTML. In this paper we show that the LF-DTML problem is P-complete. Furthermore, we show that even when restricted to planar graphs, the LF-DTML problem remains P-complete.

AB - The Different Than Majority Labelling (DTML) problem has a simple polynomial time sequential algorithm. The labelling given by this algorithm is called the Lexicographical First DTML. In this paper we show that the LF-DTML problem is P-complete. Furthermore, we show that even when restricted to planar graphs, the LF-DTML problem remains P-complete.

UR - https://www.scopus.com/pages/publications/0025522243

U2 - 10.1016/0304-3975(90)90026-E

DO - 10.1016/0304-3975(90)90026-E

M3 - Article

AN - SCOPUS:0025522243

SN - 0304-3975

VL - 76

SP - 343

EP - 351

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 2-3

ER -

A P-complete graph partition problem

Abstract

Access to Document

Other files and links

Fingerprint

Cite this