ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
NP-completeness of the domatic number problem on circular arc graphs
Full text PdfPdf (33 KB)
Source ACM Southeast Regional Conference archive
Proceedings of the 37th annual Southeast regional conference (CD-ROM) table of contents
Article No. 43  
Year of Publication: 1999
ISBN:1-58113-128-3
Author
Alan P. Sprague  Department of Computer and Information Sciences, University of Alabama at Birmingham, Birmingham, Alabama
Sponsor
ACM: Association for Computing Machinery
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 2,   Downloads (12 Months): 14,   Citation Count: 1
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/306363.306416
What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

 
1
BONUCCELLI, M. A., "Dominating sets and domatic number of circular arc graphs," Discrete Appl. Math, vol. 12, pp. 203-213, 1985.
 
2
GAREY, M. R., JOHNSON, D. S., MILLER, G. L., AND PAPADIMITRIOU, C. H., "The complexity of coloring circular arcs and chords," SIAM J. Alg. Disc. Meth., vol. 1, pp. 216-227, 1980.
3
Akihiro Hashimoto , James Stevens, Wire routing by optimizing channel assignment within large apertures, Proceedings of the 8th workshop on Design automation, p.155-169, June 28-30, 1971, Atlantic City, New Jersey, United States  [doi>10.1145/800158.805069]
 
4
Haim Kaplan , Ron Shamir, The domatic number problem on some perfect graph families, Information Processing Letters, v.49 n.1, p.51-56, Jan. 14, 1994  [doi>10.1016/0020-0190(94)90054-X]
 
5
TUCKER, A., "An efficient test for circular arc graphs," SIAM J. Computing, vol. 9, pp. 1-24, 1980.

CITED BY
Sriram V. Pemmaraju , Imran A. Pirwani, Energy conservation via domatic partitions, Proceedings of the seventh ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS


General Terms:
Design, Measurement, Performance, Theory

Collaborative Colleagues:
Alan P. Sprague: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player