Efficient Domination on Permutation Graphs and Trapezoid Graphs

Y. Daniel Liang; C. L. Lu; C. Y. Tang

doi:10.1007/BFb0045090

Efficient Domination on Permutation Graphs and Trapezoid Graphs

Y. Daniel Liang, C. L. Lu, C. Y. Tang

Computer Science

Research output: Contribution to book or proceeding › Chapter

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.

Original language	American English
Title of host publication	Proceedings of Third Annual International Computing and Combinatorics Conference
DOIs	https://doi.org/10.1007/BFb0045090
State	Published - Aug 1997

Keywords

Bipartite Graph
Chordal Graph
Interval Graph
Perfect Code
Split Graph

DC Disciplines

Computer Sciences

Access to Document

10.1007/BFb0045090License: Unspecified

Cite this

@inbook{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. ",

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

author = "Liang, {Y. Daniel} and Lu, {C. L.} and Tang, {C. Y.}",

note = "This book constitutes the refereed proceedings of the Third Annual International Computing and Combinatorics Conference, COCOON'97, held in Shanghai, China, in August 1997.The volume presents 53 revised full papers selected from a total of 106 submissions. The papers are organized in sections on...",

year = "1997",

month = aug,

doi = "10.1007/BFb0045090",

language = "American English",

booktitle = "Proceedings of Third Annual International Computing and Combinatorics Conference",

}

TY - CHAP

T1 - Efficient Domination on Permutation Graphs and Trapezoid Graphs

AU - Liang, Y. Daniel

AU - Lu, C. L.

AU - Tang, C. Y.

N1 - This book constitutes the refereed proceedings of the Third Annual International Computing and Combinatorics Conference, COCOON'97, held in Shanghai, China, in August 1997.The volume presents 53 revised full papers selected from a total of 106 submissions. The papers are organized in sections on...

PY - 1997/8

Y1 - 1997/8

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.

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.

KW - Bipartite Graph

KW - Chordal Graph

KW - Interval Graph

KW - Perfect Code

KW - Split Graph

UR - https://www.springer.com/gp/book/9783540633570

U2 - 10.1007/BFb0045090

DO - 10.1007/BFb0045090

M3 - Chapter

BT - Proceedings of Third Annual International Computing and Combinatorics Conference

ER -

Efficient Domination on Permutation Graphs and Trapezoid Graphs

Abstract

Keywords

DC Disciplines

Access to Document

Other files and links

Fingerprint

Cite this