Callum Lerwick wrote:
On Tue, 2009-03-24 at 23:40 +0900, robert song wrote:
  
Hello, everyone.
Now I am using Pettis-Hansen method as follows to reorder functions.
http://www.cs.virginia.edu/kim/courses/cs771/papers/pettis90profile.pdf
    

http://portal.acm.org/citation.cfm?id=93550

Paper was published in 1990.

  
But I found that the algorithm has its patent as below.
http://www.freepatentsonline.com/EP0459192.html
    

I took a closer look. That's a European patent:

http://v3.espacenet.com/publicationDetails/biblio?CC=EP&NR=0459192&KC=&FT=E

Which according to this:

http://www.ipo.gov.uk/types/patent/p-os/p-journal/p-pj/p-pj-epuk?startYear=2009&startMonth=January&startDay=28th+-+6245&endYear=2009&endMonth=January&endDay=28th+-+6245&filter=EP0459192&perPage=10&status=All&sort=Publication+Date

It "Ceased" on May 8, 2008.

There's some stuff about "Ceased through non-payment of renewal fee" and
"Lapsed" at the end of this page:

http://v3.espacenet.com/publicationDetails/inpadoc?CC=EP&NR=0459192A2&KC=A2&FT=D&date=19911204&DB=&locale=

I don't know anything about European patents but that sounds like
"Expired" to me.

The US patent seems to be here:

http://www.patentstorm.us/patents/5212794.html

With an "estimated" expiration date of June 1, 2010.

Is HP known for being a patent troll? What is their track record with
open source? (I honestly don't really know.)

This patent doesn't seem like much of a threat anymore and in a little
over a year will be completely gone. Imagine the ruckus if HP started
trying to sue everyone over gcc. Why would they bother with such a PR
nightmare on a patent that's a year from expiring? (The answer is,
getting bought out or taken over by patent trolls, like what happened to
SCO...)

... I of course am not a lawyer.
  
HP is just one of many companies that now derives more benefit from open source projects than if they were to try to enforce basically worthless patents.  There are tens of thousands if not hundreds of thousands of worthless patents filed that are never enforced and never challenged.  They just die a quiet death.  Especially in the days before the internet, many patents got filed on ideas that had already been in commercial products for years.  And the patent examiners never found these instances back then.  Probably because they didn't look too hard.  I wouldn't worry that much about these dubious patents.  You can drive yourself crazy trying to patent search everything about software code techniques.

Regards,
Gerry