Volume 77 - Theory of Computing 2008

Fourteenth Computing: The Australasian Theory Symposium (CATS2008), Wollongong, NSW, January 2008

Australian Computer Science Communications, Vol. 30, No. 4

This volume contains proceedings of the Fourteenth Computing: The Australasian Theory Symposium (CATS2008), Wollongong, NSW, January 2008. Where indicated, the paper is available for download in PDF or Postscript format.

The series is published by, and most papers are copyright of, the Australian Computer Society Inc. Reproduction for academic research and not-for-profit purposes is granted provided the copyright notice on the first page of each paper is included.

Edited by James Harland and Prabhu Manyem. Published January 2008. ISBN-13 978-1-920682-58-3. ISSN 1445-1336. 17 Papers, xvi+146 pages, softcover. BiBTeX file for Volume. Complete Volume.

Acceptance Rate Information. The full papers in this volume were peer refereed, in full, by an international programme committee. The acceptance rate was 60.7% (17 from 28).

Volume Citation

Harland, J. and Manyem, P., Eds. (2008). Theory of Computing 2008. Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008). CRPIT. 77. Wollongong, NSW, Australia, ACS.

Papers Included in the Volume

Allender, E. (2008). Chipping Away at P vs NP: How Far Are We from Proving Circuit Size Lower Bounds?. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds., ACS. 3.
Asahiro, Y., Miyano, E. and Ono, H. (2008). Graph Classes and the Complexity of the Graph Orientation Minimizing the Maximum Weighted Outdegree. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds., ACS. 97-106.
Asquith, M., Gudmundsson, J. and Merrick, D. (2008). An ILP for the metro-line crossing problem. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds., ACS. 49-56.
Bai, S. and Brent, R.P. (2008). On the Efficiency of Pollard's Rho Method for Discrete Logarithms. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds., ACS. 125-131.
Bunder, M. (2008). The Inhabitation Problem for Intersection Types. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds., ACS. 7-14.
Chang, C.-L., Ti, Y.-W. and Lyuu, Y.-D. (2008). Testing Embeddability Between Metric Spaces. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds., ACS. 117-124.
Groves, L. (2008). Verifying Michael and Scott's Lock-Free Queue Algorithm using Trace Reduction. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds., ACS. 133-142.
Huang, X., Jiao, L. and Lu, W. (2008). Weak Parametric Failure Equivalences and Their Congruence Formats. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds., ACS. 15-26.
Huston, S., Puchinger, J. and Stuckey, P. (2008). The Core Concept for 0/1 Integer Programming. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds., ACS. 39-47.
Levit, V. and Mandrescu, E. (2008). Well-covered Graphs and Greedoids. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds., ACS. 87-91.
Mathieson, L. and Szeider, S. (2008). The Parameterized Complexity of Regular Subgraph Problems and Generalizations. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds., ACS. 79-86.
Miller, M., Nguyen, M.H. and Pineda-Villavicencio, G. (2008). On the Non-existence of Even Degree Graphs with Diameter 2 and Defect 2. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds., ACS. 93-95.
Morozova, E. (2008). A Multidimensional Bisection Method for Unconstrained Minimization Problem. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds., ACS. 57-62.
Mujuni, E. and Rosamond, F. (2008). Parameterized Complexity of the Clique Partition Problem. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds., ACS. 75-78.
Ohrimenko, O. and Stuckey, P. (2008). Modelling for Lazy Clause Generation. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds., ACS. 27-37.
Ruskey, F. and Williams, A. (2008). Generating Balanced Parentheses and Binary Trees by Prefix Shifts. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds., ACS. 107-115.
Samer, M. and Szeider, S. (2008). Tractable Cases of the Extended Global Cardinality Constraint. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds., ACS. 67-74.
Shah, N.H., Gor, A.S. and Wee, H. (2008). Optimal Joint Vendor-Buyer Inventory Strategy for Deteriorating Items with Salvage Value. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds., ACS. 63-66.

Papers listed: 18