Efficient Domination on Permutation Graphs and Trapezoid Graphs

Y. Daniel Liang; Chin Lung Lu; Chuan Yi Tang

doi:10.1007/BFb0045090

Efficient Domination on Permutation Graphs and Trapezoid Graphs

Y. Daniel Liang, Chin Lung Lu, Chuan Yi Tang

Computer Science

Research output: Contribution to book or proceeding › Conference article › peer-review

24 Scopus citations

Abstract

The weighted efficient domination problem was solved in O(nm) time for cocomparability graphs [6]. This paper investigates whether more efficient algorithms can be found for permutation graphs and trapezoid graphs - subclasses of cocomparability graphs. Specifically, we present an O(n + m) algorithm for the weighted efficient domination problem on permutation graphs and an O(n log log n + m) algorithm on trapezoid graphs, where m¯denotes the number of edges in the complement of G.

Original language	English
Title of host publication	Computing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings
Editors	Tao Jiang, D.T. Lee
Publisher	Springer Verlag
Pages	232-241
Number of pages	10
ISBN (Print)	354063357X, 9783540633570
DOIs	https://doi.org/10.1007/BFb0045090
State	Published - 1997
Event	3rd Annual International Computing and Combinatorics Conference, COCOON 1997 - Shanghai, China Duration: Aug 20 1997 → Aug 22 1997

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1276
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	3rd Annual International Computing and Combinatorics Conference, COCOON 1997
Country/Territory	China
City	Shanghai
Period	08/20/97 → 08/22/97

Scopus Subject Areas

Theoretical Computer Science
General Computer Science

Disciplines

Computer Sciences

Keywords

Bipartite Graph
Chordal Graph
Interval Graph
Perfect Code
Split Graph

Access to Document

10.1007/BFb0045090License: Unspecified

Cite this

Daniel Liang, Y., Lu, C. L., & Tang, C. Y. (1997). Efficient Domination on Permutation Graphs and Trapezoid Graphs. In T. Jiang, & D. T. Lee (Eds.), Computing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings (pp. 232-241). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1276). Springer Verlag. https://doi.org/10.1007/BFb0045090

Daniel Liang, Y. ; Lu, Chin Lung ; Tang, Chuan Yi. / Efficient Domination on Permutation Graphs and Trapezoid Graphs. Computing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings. editor / Tao Jiang ; D.T. Lee. Springer Verlag, 1997. pp. 232-241 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{817740a8293d429da3ad32a4a0372759,

title = "Efficient Domination on Permutation Graphs and Trapezoid Graphs",

abstract = "The weighted efficient domination problem was solved in O(nm) time for cocomparability graphs [6]. This paper investigates whether more efficient algorithms can be found for permutation graphs and trapezoid graphs - subclasses of cocomparability graphs. Specifically, we present an O(n + m) algorithm for the weighted efficient domination problem on permutation graphs and an O(n log log n + m) algorithm on trapezoid graphs, where m¯denotes the number of edges in the complement of G.",

keywords = "Bipartite Graph, Chordal Graph, Interval Graph, Perfect Code, Split Graph",

author = "{Daniel Liang}, Y. and Lu, {Chin Lung} and Tang, {Chuan Yi}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1997.; 3rd Annual International Computing and Combinatorics Conference, COCOON 1997 ; Conference date: 20-08-1997 Through 22-08-1997",

year = "1997",

doi = "10.1007/BFb0045090",

language = "English",

isbn = "354063357X",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "232--241",

editor = "Tao Jiang and D.T. Lee",

booktitle = "Computing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings",

address = "Germany",

}

Daniel Liang, Y, Lu, CL & Tang, CY 1997, Efficient Domination on Permutation Graphs and Trapezoid Graphs. in T Jiang & DT Lee (eds), Computing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1276, Springer Verlag, pp. 232-241, 3rd Annual International Computing and Combinatorics Conference, COCOON 1997, Shanghai, China, 08/20/97. https://doi.org/10.1007/BFb0045090

Efficient Domination on Permutation Graphs and Trapezoid Graphs. / Daniel Liang, Y.; Lu, Chin Lung; Tang, Chuan Yi.
Computing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings. ed. / Tao Jiang; D.T. Lee. Springer Verlag, 1997. p. 232-241 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1276).

Research output: Contribution to book or proceeding › Conference article › peer-review

TY - GEN

T1 - Efficient Domination on Permutation Graphs and Trapezoid Graphs

AU - Daniel Liang, Y.

AU - Lu, Chin Lung

AU - Tang, Chuan Yi

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1997.

PY - 1997

Y1 - 1997

N2 - The weighted efficient domination problem was solved in O(nm) time for cocomparability graphs [6]. This paper investigates whether more efficient algorithms can be found for permutation graphs and trapezoid graphs - subclasses of cocomparability graphs. Specifically, we present an O(n + m) algorithm for the weighted efficient domination problem on permutation graphs and an O(n log log n + m) algorithm on trapezoid graphs, where m¯denotes the number of edges in the complement of G.

AB - The weighted efficient domination problem was solved in O(nm) time for cocomparability graphs [6]. This paper investigates whether more efficient algorithms can be found for permutation graphs and trapezoid graphs - subclasses of cocomparability graphs. Specifically, we present an O(n + m) algorithm for the weighted efficient domination problem on permutation graphs and an O(n log log n + m) algorithm on trapezoid graphs, where m¯denotes the number of edges in the complement of G.

KW - Bipartite Graph

KW - Chordal Graph

KW - Interval Graph

KW - Perfect Code

KW - Split Graph

UR - http://www.scopus.com/inward/record.url?scp=84947716525&partnerID=8YFLogxK

U2 - 10.1007/BFb0045090

DO - 10.1007/BFb0045090

M3 - Conference article

SN - 354063357X

SN - 9783540633570

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 232

EP - 241

BT - Computing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings

A2 - Jiang, Tao

A2 - Lee, D.T.

PB - Springer Verlag

T2 - 3rd Annual International Computing and Combinatorics Conference, COCOON 1997

Y2 - 20 August 1997 through 22 August 1997

ER -

Daniel Liang Y, Lu CL, Tang CY. Efficient Domination on Permutation Graphs and Trapezoid Graphs. In Jiang T, Lee DT, editors, Computing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings. Springer Verlag. 1997. p. 232-241. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/BFb0045090

Efficient Domination on Permutation Graphs and Trapezoid Graphs

Abstract

Publication series

Conference

Scopus Subject Areas

Disciplines

Keywords

Access to Document

Other files and links

Fingerprint

Cite this