User:BIOalgorithm/sandbox: Difference between revisions

Revision as of 23:23, 12 July 2012

Latest revision as of 16:00, 17 May 2021

(4 intermediate revisions by 2 users not shown)

Line 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 147 ⟶ 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 164 ⟶ 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 186 ⟶ 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 193 ⟶ 202:

| volume = 15

| pages = 835–855

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

*{{citation

| last1 = Gilmore | first1 = P. C.

Line 215 ⟶ 224:

| volume = 40

| pages = 1108–1133

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

*{{citation

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

Line 224 ⟶ 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 236 ⟶ 245:

| year = 1994

| pages = 309–317

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

== External links ==

Line 245 ⟶ 254:

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

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

{{DEFAULTSORT:Interval Graph}}

[[Category:Perfect graphs]]

Line 254 ⟶ 264:

[[hu:Intervallumgráf]]

[[pl:Graf przedziałowy]]

-->