シーケンスペア
シーケンスペア(1 3 2 4 5 6 ; 2 1 4 6 3 5)の水平制約グラフを図7の左に、垂直制約グラフを右に示す。
ところで、上記の方法はスライス木のデコード時間( O ( n ) {\displaystyle O(n)} )よりも遅いため、確率的探索の1回毎の解の評価に時間がかかってしまい、良質な解を得るのにスライス木よりも多くの時間を要してしまう。これに対し、2001年にシーケンスペア上の最長共通部分列(longest common subsequence)を求めて O ( n log  log  n ) {\displaystyle O(n\log \log n)} 時間でデコードするFAST-SPが、2003年にはシーケンスペアの冗長性を排除することで O ( n ) {\displaystyle O(n)} 時間でデコードするSelected Sequence-pairが提案されている。
一般構造の表現方法についてブレークスルーになったのは、1994年に当時北陸先端科学技術大学院大学の学生であった中武らにより提案された、BSG(Bounded Sliceline Grid)と呼ばれる構造である。小さい規模のBSG構造を図4に示すが、その構造は四畳半構造の連続となっていて興味深い。
BSGを斜めの格子構造で説明し、代数表現にしたのがシーケンスペアである。シーケンスペアは、BSG提案の一年後である1995年に北陸先端科学技術大学院大学の学生であった村田らによって提案された。シーケンスペアという名前の由来は、矩形名の順列(sequence)の対(pair)によって、矩形同士の相対位置関係を表すことから来ている。
余談だが、BSGもシーケンスペアも、その理論の証明には北陸先端大近辺の温泉が一役買っている。どちらも議論の際には格子構造を考える必要があるが、温泉のタイルが格子状であり、湯船につかりながら温泉が閉店するまでタイルを見つめて考えていた、とのことである。それもあってシーケンスペアの論文はよく練られて掲載されたためか、Google Scholarによれば約330本の論文に引用されているとのことで、この分野では突出した引用件数である。また、これらBSGとシーケンスペアの著者は同じ4名(中武、村田、藤吉、梶谷)で、現在村田はEDAツールベンダーを起業、他3名は東京と福岡で大学教員を続けている。