Cordial labelling of butterfly networks and mesh of trees
- Authors: Miller, Mirka , Rajan, Bharati , Rajasingh, Indra , Manuel, Paul
- Date: 2006
- Type: Text , Conference paper
- Relation: Paper presented at AWOCA 2006, 17th Australasian Workshop on Combinatorial Algorithms, Uluru, Australia : 13th July, 2006
- Full Text: false
- Reviewed:
- Description: E1
- Description: 2003001646
On graphs of maximum size with given girth and order
- Authors: Miller, Mirka , Lin, Yuqing , Brankovic, Ljiljana , Tang, Jianmin
- Date: 2006
- Type: Text , Conference paper
- Relation: Paper presented at AWOCA 2006, 17th Australasian Workshop on Combinatorial Algorithms, Uluru, Australia : 13th July, 2006
- Full Text: false
- Reviewed:
- Description: E1
- Description: 2003001918
Polynomial-time maximisation classes : Syntactic hierarchy
- Authors: Manyem, Prabhu
- Date: 2006
- Type: Text , Conference paper
- Relation: Paper presented at AWOCA 2006, 17th Australasian Workshop on Combinatorial Algorithms, Uluru, Australia : 13th July, 2006
- Full Text:
- Reviewed:
- Description: In Descriptive Complexity, there is a vast amount of literature on decision problems, and their classes such as textbf{P, NP, L and NL}. ~ However, research on the descriptive complexity of optimisation problems has been limited. In a previous paper [Man], we characterised the optimisation versions of textbf{P} via expressions in second order logic, using universal Horn formulae with successor relations. In this paper, we study the syntactic hierarchy within the class of polynomially bound maximisation problems. We extend the result in the previous paper by showing that the class of polynomially-bound bf{NP} (not just bf{P}) maximisation problems can be expressed in second-order logic using Horn formulae with successor relations. Finally, we provide an application --- we show that the Bin Packing problem with online LIB constraints can be approximated to within a $Theta(log n)$ bound, by providing a syntactic characterisation for this problem.
- Description: E1
- Description: 2003001917