Search

Your search keyword '"Chang, Maw-Shang"' showing total 179 results
Start Over "Chang, Maw-Shang"

Refine your results

more »

more »

more »

more »

more »
179 results on '"Chang, Maw-Shang"'

1. Independent sets in edge-clique graphs

Author

Chang, Maw-Shang, Kloks, Ton, and Liu, Ching-Hao

Subjects
Mathematics - Combinatorics, Computer Science - Discrete Mathematics
Abstract

We show that the edge-clique graphs of cocktail party graphs have unbounded rankwidth. This, and other observations lead us to conjecture that the edge-clique cover problem is NP-complete for cographs. We show that the independent set problem on edge-clique graphs of cographs and of distance-hereditary graphs can be solved in O(n^4) time. We show that the independent set problem on edge-clique graphs of graphs without odd wheels remains NP-complete., Comment: arXiv admin note: incorporates arXiv:1205.2483

Published
2012

2. Edge-clique graphs of cocktail parties have unbounded rankwidth

Author

Chang, Maw-Shang, Kloks, Ton, and Liu, Ching-Hao

Subjects
Computer Science - Discrete Mathematics, Mathematics - Combinatorics
Abstract

In an attempt to find a polynomial-time algorithm for the edge-clique cover problem on cographs we tried to prove that the edge-clique graphs of cographs have bounded rankwidth. However, this is not the case. In this note we show that the edge-clique graphs of cocktail party graphs have unbounded rankwidth.

Published
2012

7. Recognition of Probe Ptolemaic Graphs : (Extended Abstract)

Author

Chang, Maw-Shang, Hung, Ling-Ju, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Iliopoulos, Costas S., editor, and Smyth, William F., editor

Published
2011
Full Text
View/download PDF

8. Certifying Algorithms for the Path Cover and Related Problems on Interval Graphs

Author

Hung, Ruo-Wei, Chang, Maw-Shang, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Taniar, David, editor, Gervasi, Osvaldo, editor, Murgante, Beniamino, editor, Pardede, Eric, editor, and Apduhan, Bernady O., editor

Published
2010
Full Text
View/download PDF

9. Block-Graph Width

Author

Chang, Maw-Shang, Hung, Ling-Ju, Kloks, Ton, Peng, Sheng-Lung, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Chen, Jianer, editor, and Cooper, S. Barry, editor

Published
2009
Full Text
View/download PDF

10. Probe Ptolemaic Graphs

Author

Chandler, David B., Chang, Maw-Shang, Kloks, Ton, Le, Van Bang, Peng, Sheng-Lung, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Hu, Xiaodong, editor, and Wang, Jie, editor

Published
2008
Full Text
View/download PDF

11. New Fixed-Parameter Algorithms for the Minimum Quartet Inconsistency Problem

Author

Chang, Maw-Shang, Lin, Chuang-Chieh, Rossmanith, Peter, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Grohe, Martin, editor, and Niedermeier, Rolf, editor

Published
2008
Full Text
View/download PDF

12. The 3-Steiner Root Problem

Author

Chang, Maw-Shang, Ko, Ming-Tat, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Brandstädt, Andreas, editor, Kratsch, Dieter, editor, and Müller, Haiko, editor

Published
2007
Full Text
View/download PDF

13. Partitioned Probe Comparability Graphs

Author

Chandler, David B., Chang, Maw-Shang, Kloks, Ton, Liu, Jiping, Peng, Sheng-Lung, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Fomin, Fedor V., editor

Published
2006
Full Text
View/download PDF

14. Linear-Time Algorithms for Tree Root Problems

Author

Chang, Maw-Shang, Ko, Ming-Tat, Lu, Hsueh-I, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Arge, Lars, editor, and Freivalds, Rusins, editor

Published
2006
Full Text
View/download PDF

15. Recognition of Probe Cographs and Partitioned Probe Distance Hereditary Graphs

Author

Chandler, David B., Chang, Maw-Shang, Kloks, Ton, Liu, Jiping, Peng, Sheng-Lung, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Cheng, Siu-Wing, editor, and Poon, Chung Keung, editor

Published
2006
Full Text
View/download PDF

16. On Probe Permutation Graphs

Author

Chandler, David B., Chang, Maw-Shang, Kloks, Antonius J. J., Liu, Jiping, Peng, Sheng-Lung, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Cai, Jin-Yi, editor, Cooper, S. Barry, editor, and Li, Angsheng, editor

Published
2006
Full Text
View/download PDF

19. An Efficient Exact Algorithm for the Minimum Ultrametric Tree Problem

Author

Chen, Hsin-Fu, Chang, Maw-Shang, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Fleischer, Rudolf, editor, and Trippen, Gerhard, editor

Published
2005
Full Text
View/download PDF

21. Maximum Clique Transversals

Author

Chang, Maw-Shang, Kloks, Ton, Lee, Chuan-Min, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Brandstädt, Andreas, editor, and Le, Van Bang, editor

Published
2001
Full Text
View/download PDF

22. On the Tree-Degree of Graphs

Author

Chang, Maw-Shang, Müller, Haiko, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Brandstädt, Andreas, editor, and Le, Van Bang, editor

Published
2001
Full Text
View/download PDF

33. 20-Relative neighborhood graphs are Hamiltonian

Author

Chang, Maw Shang, Tang, C. Y., Lee, R. C. T., Goos, G., editor, Hartmanis, J., editor, Barstow, D., editor, Brauer, W., editor, Brinch Hansen, P., editor, Gries, D., editor, Luckham, D., editor, Moler, C., editor, Pnueli, A., editor, Seegmüller, G., editor, Stoer, J., editor, Wirth, N., editor, Asano, Tetsuo, editor, Ibaraki, Toshihide, editor, Imai, Hiroshi, editor, and Nishizeki, Takao, editor

Published
1990
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results