User:BIOalgorithm/sandbox: Difference between revisions

Revision as of 18:53, 12 July 2012

Latest revision as of 16:00, 17 May 2021

(6 intermediate revisions by 2 users not shown)

Line 22:

All of the algorithms above rely on seeking an ordering of the maximal [[Clique (graph theory)|clique]]s of ''G'' that is consecutive with respect to vertex inclusion, and '''the precomputation of all maximal cliques''' is required. A simpler off-line recognition algorithm was provided by {{harvtxt|W. L. Hsu|1992}} which directly places the intervals ''without'' precomputing maximal cliques<ref>W. L. Hsu (1992)</ref>.

===Habib et al.'s Algorithm===

===Hsu's Algorithm===

Line 98 ⟶ 96:

12 '''end else'''

:Then we can get the S-decomposition tree. One thing to note is that we need to '''avoid cycle''' in G" while building it. To do this, for each group of connected edges(and vertices), we assign one represented vertex to all edges(and all vertices) in the group, then the check before each edge addition becomes easy. For example, before we add the new edge E(u, v), we only need to compare the represented vertex of u and that of v, no cycle will occur if the two are different.

* Test each S-prime component to see if it is an interval graph.

:This can be done by truly building the truecorresponding interval graph; first adding the non-simplicial vertices, then adding the simplicial vertices through a linear scan. The second part is intuitive; the first part needs more detailed discussion.

'''Lemma'''

Let u_k be the next interval to be placed, which is not a neighbor of previously chosen intervals. Let u_j be the parent of u_k and u_i be the parent of u_j in the BFS-tree. It can be determined uniquely which endpoints of u_j or u_i is contained in u_k.

There are three cases, place each edge according to its category.

* Case 1: (f(u_i), u_j) ∉ E. If u_i ,u_k are on the different side of u_j, u_k would contain u_j.

* Case 2: (f(u_k), u_j ) ∉ E. Again, if u_i, u_k are on the different side of u_j, u_k would contain u_j.

* Case 3: (f(u_j), u_k) ∉ E and (f(u_j), u_i) ∉ E. If u_i ,u_k are on the different sides of u_j, u_k cannot be adjacent to u_i.

:(''f''(''u'') := ''u'''s neighbor vertex with the smallest ''π''-index.)

==Related families of graphs==

Line 149 ⟶ 156:

| title = A partial ''k''-arboretum of graphs with bounded treewidth

| volume = 209

| year = 1998| hdl = 1874/18312 }}.

*{{citation

| last = Hsu | first = W. L.

| issue = 11-1611–16

| journal = [[Lecture Notes in Computer Science]]

| title = A new test for interval graphs

Line 166 ⟶ 173:

| doi = 10.1016/S0022-0000(76)80045-1

| issue = 3}}.

* {{cite book|year=1978|last=Cohen|first=Joel E.|authorlink=Joel E. Cohen|title=Food webs and niche space|series=Monographs in Population Biology|volume=11|___location=Princeton, NJ|publisher=[http://press.princeton.edu/titles/324.html Princeton University Press]|pages=xv+1–190|ref=harv|isbn=978-0-691-08202-8}}

*{{citation

| last = Eckhoff | first = Jürgen

Line 188 ⟶ 195:

| year = 1997

| mr = 1432221}}.

* {{cite book|last=Fishburn|first=Peter C.|authorlink=Peter C. Fishburn|year=1985|title=Interval orders and interval graphs: A study of partially ordered sets|series=Wiley-Interscience Series in Discrete Mathematics|___location=New York|publisher=John Wiley & Sons|ref=harv|mr=|isbn=}}

*{{citation

| author1-link = D. R. Fulkerson | last1 = Fulkerson | first1 = D. R. | last2 = Gross | first2 = O. A.

Line 195 ⟶ 202:

| volume = 15

| pages = 835–855

| year = 1965| issue = 3 | doi = 10.2140/pjm.1965.15.835 }}.

*{{citation

| last1 = Gilmore | first1 = P. C.

Line 217 ⟶ 224:

| volume = 40

| pages = 1108–1133

| year = 1993| doi = 10.1145/174147.169675 }}.

*{{citation

| last1 = Habib | first1 = Michel | last2 = McConnell | first2 = Ross

Line 226 ⟶ 233:

| pages = 59–84

| year = 2000

| issue = 1–2 | url = http://www.cs.colostate.edu/~rmm/lexbfs.ps

| doi = 10.1016/S0304-3975(97)00241-7}}.

*{{citation

Line 238 ⟶ 245:

| year = 1994

| pages = 309–317

| doi = 10.1093/bioinformatics/10.3.309| pmid = 7922688 }}.

== External links ==

Line 247 ⟶ 254:

* {{mathworld | urlname = IntervalGraph | title = Interval graph}}

<!-- Comment out categories and interwikis while this is in userspace

{{DEFAULTSORT:Interval Graph}}

[[Category:Perfect graphs]]

Line 256 ⟶ 264:

[[hu:Intervallumgráf]]

[[pl:Graf przedziałowy]]

-->