Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Індиферентний граф це неорієнтований граф побудований призначенням дійсного числа кожній вершині і з єднанням двох верши

Індиферентний граф

Індиферентний граф

Індиферентний граф — це неорієнтований граф, побудований призначенням дійсного числа кожній вершині і з'єднанням двох вершин ребром, коли їхні числа відрізняються не більше ніж на одиницю. Індиферентні графи є також графами перетинів множин одиничних відрізків або інтервалів з визначеною властивістю вкладення (ніякий інтервал не містить будь-якого іншого). Ґрунтуючись на цих двох типах інтервальних подань, ці графи називаються також графами одиничних відрізків або власними інтервальними графами. Індиферентні графи утворюють підклас інтервальних графів.

image
Індиферентний граф, утворений на множині точок на дійсній прямій з'єднанням пар, відстань між якими не перевищує 1

Еквівалентні описи

image
Заборонені породжені підграфи для індиферентних графів — клешня, «сонце», «мережа» і цикли довжиною чотири і більше (внизу)

Скінченні індиферентні графи можна еквівалентно описати як

  • Графи перетинів одиничних відрізків
  • Графи перетинів множин інтервалів, ніякі два з яких не вкладені один в інший
  • Інтервальні графи без клешень
  • Графи, які не містять породжених підграфів, ізоморфних клешні K1,3, «мережі» (трикутнику з трьома додатковими вершинами, приєднаними до кожної з вершин трикутника), «сонцю» (трикутнику з трьома приєднаними трикутниками, які мають спільні ребра з центральним трикутником), або «дірці» (циклу довжини чотири і більше)
  • Графи непорівнянності [en]
  • Неорієнтовані графи, які мають лінійний порядок, такий, що для кожного шляху з трьох вершин image, вершини якого впорядковані image-image-image, кінцеві вершини image і image суміжні
  • Графи, які не мають астральних трійок, трьох вершин, з'єднаних попарно шляхами, які не проходять через третю вершину, а також не містять двох суміжних вершин, одночасно суміжних вершині з околу третьої вершини.
  • Графи, в яких кожна компонента містить шлях, у якому кожна кліка компоненти утворює неперервний підшлях
  • Графи, вершини яких можна пронумерувати так, що будь-який найкоротший шлях утворює монотонну послідовність
  • Графи, матриці суміжності яких можна впорядкувати так, що в кожному рядку і кожному стовпці ненульові елементи утворюють неперервні інтервали, суміжні діагоналі матриці
  • Породжені підграфи степенів безхордових шляхів
  • [en], які мають [en] у вигляді гусениці

Для нескінченних графів деякі з цих визначень можуть дати різні графи.

Властивості

Оскільки індиферентні графи є окремим випадком інтервальних графів, індиферентні графи мають усі властивості інтервальних графів. Зокрема, вони є окремим випадком хордальних графів і досконалих графів. Ці графи є також окремим випадком колових графів, що хибно для інтервальних графів загального вигляду.

У моделі Ердеша — Реньї випадкових графів граф з image вершини, число ребер якого істотно менше від image, буде з великою ймовірністю індиферентним графом, тоді як граф з числом ребер, істотно більшим від image, з великою ймовірністю не буде індиферентним графом.

[en] довільного графу image на одиницю менша від розміру найбільшої кліки в індиферентному графі, який містить image як підграф і вибраний для мінімізації розміру найбільшої кліки. Це властивість утворює паралелі, подібні до зв'язку між шляховою шириною та інтервальними графами, а також між деревною шириною та хордальними графами. Слабше поняття ширини, клікова ширина, може бути довільно великою на індиферентних графах. Однак будь-який власний підклас індиферентних графів, не замкнутий відносно породжених підграфів, має обмежену клікову ширину.

Будь-який зв'язний індиферентний граф містить гамільтонів шлях. Індиферентний граф має гамільтонів граф тоді і тільки тоді, коли він двосв'язний.

Індиферентні графи задовольняють [en] — вони єдиним чином визначаються їхніми підграфами з видаленою вершиною.

Алгоритми

Як і з багатовимірними графами одиничних кругів, можна перетворити множину точок на її індиферентний граф або множину одиничних відрізків на її граф одиничних відрізків за лінійний час, якщо вимірювати в термінах розміру початкового графу. Алгоритм округлює точки (або центри інтервалів) до найближчого меншого цілого числа, використовує геш-таблицю для знаходження всіх пар точок, чиї округлені значення відрізняються не більше ніж на одиницю (), і відбирає в отриманому списку пари, неокруглені значення яких лежать не далі ніж на одиницю одне від одного.

Можна перевірити, чи є даний граф індиферентним за лінійний час за допомогою PQ-дерев для побудови інтервальних подань графу і потім перевірки, чи задовольняє впорядкування вершин, похідне від цього подання, властивостям індиферентного графу. Можна також заснувати алгоритм розпізнавання для індиферентних графів на алгоритмах розпізнавання для хордального графу. Деякі альтернативні алгоритми розпізнавання за лінійний час ґрунтуються на пошуку в ширину або на лексикографічному пошуку в ширину, а не на зв'язку між індиферентними графами і інтервальними графами .

Як тільки вершини відсортовано за їхніми числовими значеннями, які описують індиферентний граф (або за послідовністю одиничних відрізків у інтервальному поданні), той самий порядок можна використовувати для пошуку оптимального розфарбування цих графів, щоб розв'язати задачу про найкоротший шлях, побудову гамільтонових шляхів і найбільших парувань за лінійний час. Гамільтонів цикл можна знайти з правильного інтервального графу подання за час image, але, якщо граф є вхідним для завдання, цю ж задачу можна розв'язати за лінійний час, що можна узагальнити на інтервальні графи .

Задача [en] залишається NP-повною, навіть коли вона обмежена індиферентними графами. Однак вона є [en], якщо параметризувати за загальною кількістю кольорів на вході.

Застосування

У математичній психології індиферентні графи виникають із функцій корисності масштабуванням функції так, що одна одиниця представляє різницю корисності досить малою, так що для особистості одиниця може вважатися несуттєвою. У цьому застосуванні пари елементів, корисності яких досить великі, можна частково впорядкувати за відносним порядком корисності, що дає [en].

У біоінформатиці задачу додавання розфарбованого графу до правильно розфарбованого графу одиничних відрізків можна використати для моделювання виявлення помилково негативних збірок геному ДНК із фрагментів.

Див. також

  • Пороговий граф — граф, ребра якого визначаються сумами міток вершин, а не різницями міток
  • Тривіально досконалий граф — інтервальний граф, для якого кожна пара інтервалів вкладена або неперервана, а не належним чином перетинається

Примітки

  1. Roberts, 1969, с. 139–146.
  2. Bogart, West, 1999, с. 21–23.
  3. Wegner, 1967.
  4. Looges, Olariu, 1993, с. 15–25.
  5. Jackowski, 1992, с. 103–109.
  6. Gutierrez, Oubiña, 1996, с. 199–205.
  7. Mertzios, 2008, с. 332–337.
  8. Brandstädt, Hundt, Mancini, Wagner, 2010, с. 897–910.
  9. Cohen, 1982, с. 21–24.
  10. Kaplan, Shamir, 1996, с. 540–561.
  11. Golumbic, Rotics, 1999, с. 5–17.
  12. Lozin, 2008, с. 871–882.
  13. Bertossi, 1983, с. 97–101.
  14. Panda, Das, 2003, с. 153–161.
  15. von Rimscha, 1983, с. 283–291.
  16. Bentley, Stanat, Williams, 1977, с. 209–212.
  17. Corneil, Kim, Natarajan, Olariu, Sprague, 1995, с. 99–104.
  18. Herrera de Figueiredo, Meidanis, Picinin de Mello, 1995, с. 179–184.
  19. Corneil, 2004, с. 371–379.
  20. Hell, Huang, 2004, с. 554–570.
  21. Keil, 1985, с. 201–206.
  22. Ibarra, 2009, с. 1105–1108.
  23. Marx, 2006, с. 995–1002.
  24. Roberts, 1970, с. 243–258.
  25. Goldberg, Golumbic, Kaplan, Shamir, 2009.

Література

  • Fred S. Roberts. Indifference graphs // Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968). — Academic Press, New York, 1969. — С. 139–146.
  • Kenneth P. Bogart, Douglas B. West. A short proof that "proper=unit" // . — 1999. — Т. 201, вип. 1-3 (28 червня). — С. 21–23. — DOI:10.1016/S0012-365X(98)00310-0.
  • Wegner G. Eigenschaften der Nerven homologisch-einfacher Familien im Rn. — Göttingen, Germany : Göttingen University, 1967. — (Ph.D. thesis). Як процитовано в Hell, Huang, (2004)
  • Peter J. Looges, Stephan Olariu. Optimal greedy algorithms for indifference graphs // Computers & Mathematics with Applications. — 1993. — Т. 25, вип. 7 (28 червня). — С. 15–25. — DOI:10.1016/0898-1221(93)90308-I.
  • Zygmunt Jackowski. A new characterization of proper interval graphs // . — 1992. — Т. 105, вип. 1-3 (28 червня). — С. 103–109. — DOI:10.1016/0012-365X(92)90135-3.
  • Gutierrez M., Oubiña L. Metric characterizations of proper interval graphs and tree-clique graphs // Journal of Graph Theory. — 1996. — Т. 21, вип. 2 (28 червня). — С. 199–205. — DOI:10.1002/(SICI)1097-0118(199602)21:2<199::AID-JGT9>3.0.CO;2-M.
  • George B. Mertzios. A matrix characterization of interval and proper interval graphs // Applied Mathematics Letters. — 2008. — Т. 21, вип. 4 (28 червня). — С. 332–337. — DOI:10.1016/j.aml.2007.04.001.
  • Andreas Brandstädt, Christian Hundt, Federico Mancini, Peter Wagner. Rooted directed path graphs are leaf powers // Discrete Mathematics. — 2010. — Т. 310 (28 червня). — С. 897–910. — DOI:10.1016/j.disc.2009.10.006.
  • Joel E. Cohen. The asymptotic probability that a random graph is a unit interval graph, indifference graph, or proper interval graph // . — 1982. — Т. 40, вип. 1 (28 червня). — С. 21–24. — DOI:10.1016/0012-365X(82)90184-4.
  • Haim Kaplan, Ron Shamir. Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques // SIAM Journal on Computing. — 1996. — Т. 25, вип. 3 (28 червня). — С. 540–561. — DOI:10.1137/S0097539793258143.
  • Martin Charles Golumbic, Udi Rotics. The clique-width of unit interval graphs is unbounded // Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999). — 1999. — Т. 140. — С. 5–17. — (Congressus Numerantium)
  • Vadim V. Lozin. From tree-width to clique-width: excluding a unit interval graph // Algorithms and computation. — Springer, Berlin, 2008. — Т. 5369. — С. 871–882. — (Lecture Notes in Comput. Sci.) — DOI:10.1007/978-3-540-92182-0_76.
  • Alan A. Bertossi. Finding Hamiltonian circuits in proper interval graphs // Information Processing Letters. — 1983. — Т. 17, вип. 2 (28 червня). — С. 97–101. — DOI:10.1016/0020-0190(83)90078-9.
  • Panda B. S., Das S. K. A linear time recognition algorithm for proper interval graphs // Information Processing Letters. — 2003. — Т. 87, вип. 3 (28 червня). — С. 153–161. — DOI:10.1016/S0020-0190(03)00298-9.
  • Michael von Rimscha. Reconstructibility and perfect graphs // Discrete Mathematics. — 1983. — Т. 47, вип. 2-3 (28 червня). — С. 283–291. — DOI:10.1016/0012-365X(83)90099-7.
  • Jon L. Bentley, Donald F. Stanat, E. Hollins Williams, Jr. The complexity of finding fixed-radius near neighbors // . — 1977. — Т. 6, вип. 6 (28 червня). — С. 209–212. — DOI:10.1016/0020-0190(77)90070-9.
  • Derek G. Corneil, Hiryoung Kim, Sridhar Natarajan, Stephan Olariu, Alan P. Sprague. Simple linear time recognition of unit interval graphs // Information Processing Letters. — 1995. — Т. 55, вип. 2 (28 червня). — С. 99–104. — DOI:10.1016/0020-0190(95)00046-F.
  • Celina M. Herrera de Figueiredo, João Meidanis, Célia Picinin de Mello. A linear-time algorithm for proper interval graph recognition // Information Processing Letters. — 1995. — Т. 56, вип. 3 (28 червня). — С. 179–184. — DOI:10.1016/0020-0190(95)00133-W.
  • Derek G. Corneil. A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs // Discrete Applied Mathematics. — 2004. — Т. 138, вип. 3 (28 червня). — С. 371–379. — DOI:10.1016/j.dam.2003.07.001.
  • Pavol Hell, Jing Huang. Certifying LexBFS recognition algorithms for proper interval graphs and proper interval bigraphs // SIAM Journal on Discrete Mathematics. — 2004. — Т. 18, вип. 3 (28 червня). — С. 554–570. — DOI:10.1137/S0895480103430259.
  • J. Mark Keil. Finding Hamiltonian circuits in interval graphs // Information Processing Letters. — 1985. — Т. 20, вип. 4 (28 червня). — С. 201–206. — DOI:10.1016/0020-0190(85)90050-X.
  • Louis Ibarra. A simple algorithm to find Hamiltonian cycles in proper interval graphs // Information Processing Letters. — 2009. — Т. 109, вип. 18 (28 червня). — С. 1105–1108. — DOI:10.1016/j.ipl.2009.07.010.
  • Dániel Marx. Precoloring extension on unit interval graphs // Discrete Applied Mathematics. — 2006. — Т. 154, вип. 6 (28 червня). — С. 995–1002. — DOI:10.1016/j.dam.2005.10.008.
  • Fred S. Roberts. On nontransitive indifference // Journal of Mathematical Psychology. — 1970. — Т. 7 (28 червня). — С. 243–258. — DOI:10.1016/0022-2496(70)90047-7.
  • Paul W. Goldberg, Martin C. Golumbic, Haim Kaplan, Ron Shamir. Four strikes against physical mapping of DNA // Journal of Computational Biology. — 2009. — Т. 2, вип. 2 (28 червня). — DOI:10.1089/cmb.1995.2.139. — PMID 7497116 .

Посилання

  • Information System on Graph Class Inclusions [ 3 травня 2021 у Wayback Machine.]: unit interval graph [ 6 травня 2021 у Wayback Machine.]

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Indiferentnij graf ce neoriyentovanij graf pobudovanij priznachennyam dijsnogo chisla kozhnij vershini i z yednannyam dvoh vershin rebrom koli yihni chisla vidriznyayutsya ne bilshe nizh na odinicyu Indiferentni grafi ye takozh grafami peretiniv mnozhin odinichnih vidrizkiv abo intervaliv z viznachenoyu vlastivistyu vkladennya niyakij interval ne mistit bud yakogo inshogo Gruntuyuchis na cih dvoh tipah intervalnih podan ci grafi nazivayutsya takozh grafami odinichnih vidrizkiv abo vlasnimi intervalnimi grafami Indiferentni grafi utvoryuyut pidklas intervalnih grafiv Indiferentnij graf utvorenij na mnozhini tochok na dijsnij pryamij z yednannyam par vidstan mizh yakimi ne perevishuye 1Ekvivalentni opisiZaboroneni porodzheni pidgrafi dlya indiferentnih grafiv kleshnya sonce merezha i cikli dovzhinoyu chotiri i bilshe vnizu Skinchenni indiferentni grafi mozhna ekvivalentno opisati yak Grafi peretiniv odinichnih vidrizkiv Grafi peretiniv mnozhin intervaliv niyaki dva z yakih ne vkladeni odin v inshij Intervalni grafi bez kleshen Grafi yaki ne mistyat porodzhenih pidgrafiv izomorfnih kleshni K1 3 merezhi trikutniku z troma dodatkovimi vershinami priyednanimi do kozhnoyi z vershin trikutnika soncyu trikutniku z troma priyednanimi trikutnikami yaki mayut spilni rebra z centralnim trikutnikom abo dirci ciklu dovzhini chotiri i bilshe Grafi neporivnyannosti en Neoriyentovani grafi yaki mayut linijnij poryadok takij sho dlya kozhnogo shlyahu z troh vershin u v w displaystyle uvw vershini yakogo vporyadkovani u displaystyle u v displaystyle v w displaystyle w kincevi vershini u displaystyle u i w displaystyle w sumizhni Grafi yaki ne mayut astralnih trijok troh vershin z yednanih poparno shlyahami yaki ne prohodyat cherez tretyu vershinu a takozh ne mistyat dvoh sumizhnih vershin odnochasno sumizhnih vershini z okolu tretoyi vershini Grafi v yakih kozhna komponenta mistit shlyah u yakomu kozhna klika komponenti utvoryuye neperervnij pidshlyah Grafi vershini yakih mozhna pronumeruvati tak sho bud yakij najkorotshij shlyah utvoryuye monotonnu poslidovnist Grafi matrici sumizhnosti yakih mozhna vporyadkuvati tak sho v kozhnomu ryadku i kozhnomu stovpci nenulovi elementi utvoryuyut neperervni intervali sumizhni diagonali matrici Porodzheni pidgrafi stepeniv bezhordovih shlyahiv en yaki mayut en u viglyadi gusenici Dlya neskinchennih grafiv deyaki z cih viznachen mozhut dati rizni grafi VlastivostiOskilki indiferentni grafi ye okremim vipadkom intervalnih grafiv indiferentni grafi mayut usi vlastivosti intervalnih grafiv Zokrema voni ye okremim vipadkom hordalnih grafiv i doskonalih grafiv Ci grafi ye takozh okremim vipadkom kolovih grafiv sho hibno dlya intervalnih grafiv zagalnogo viglyadu U modeli Erdesha Renyi vipadkovih grafiv graf z n displaystyle n vershini chislo reber yakogo istotno menshe vid n 2 3 displaystyle n 2 3 bude z velikoyu jmovirnistyu indiferentnim grafom todi yak graf z chislom reber istotno bilshim vid n 2 3 displaystyle n 2 3 z velikoyu jmovirnistyu ne bude indiferentnim grafom en dovilnogo grafu G displaystyle G na odinicyu mensha vid rozmiru najbilshoyi kliki v indiferentnomu grafi yakij mistit G displaystyle G yak pidgraf i vibranij dlya minimizaciyi rozmiru najbilshoyi kliki Ce vlastivist utvoryuye paraleli podibni do zv yazku mizh shlyahovoyu shirinoyu ta intervalnimi grafami a takozh mizh derevnoyu shirinoyu ta hordalnimi grafami Slabshe ponyattya shirini klikova shirina mozhe buti dovilno velikoyu na indiferentnih grafah Odnak bud yakij vlasnij pidklas indiferentnih grafiv ne zamknutij vidnosno porodzhenih pidgrafiv maye obmezhenu klikovu shirinu Bud yakij zv yaznij indiferentnij graf mistit gamiltoniv shlyah Indiferentnij graf maye gamiltoniv graf todi i tilki todi koli vin dvosv yaznij Indiferentni grafi zadovolnyayut en voni yedinim chinom viznachayutsya yihnimi pidgrafami z vidalenoyu vershinoyu AlgoritmiYak i z bagatovimirnimi grafami odinichnih krugiv mozhna peretvoriti mnozhinu tochok na yiyi indiferentnij graf abo mnozhinu odinichnih vidrizkiv na yiyi graf odinichnih vidrizkiv za linijnij chas yaksho vimiryuvati v terminah rozmiru pochatkovogo grafu Algoritm okruglyuye tochki abo centri intervaliv do najblizhchogo menshogo cilogo chisla vikoristovuye gesh tablicyu dlya znahodzhennya vsih par tochok chiyi okrugleni znachennya vidriznyayutsya ne bilshe nizh na odinicyu i vidbiraye v otrimanomu spisku pari neokrugleni znachennya yakih lezhat ne dali nizh na odinicyu odne vid odnogo Mozhna pereviriti chi ye danij graf indiferentnim za linijnij chas za dopomogoyu PQ derev dlya pobudovi intervalnih podan grafu i potim perevirki chi zadovolnyaye vporyadkuvannya vershin pohidne vid cogo podannya vlastivostyam indiferentnogo grafu Mozhna takozh zasnuvati algoritm rozpiznavannya dlya indiferentnih grafiv na algoritmah rozpiznavannya dlya hordalnogo grafu Deyaki alternativni algoritmi rozpiznavannya za linijnij chas gruntuyutsya na poshuku v shirinu abo na leksikografichnomu poshuku v shirinu a ne na zv yazku mizh indiferentnimi grafami i intervalnimi grafami Yak tilki vershini vidsortovano za yihnimi chislovimi znachennyami yaki opisuyut indiferentnij graf abo za poslidovnistyu odinichnih vidrizkiv u intervalnomu podanni toj samij poryadok mozhna vikoristovuvati dlya poshuku optimalnogo rozfarbuvannya cih grafiv shob rozv yazati zadachu pro najkorotshij shlyah pobudovu gamiltonovih shlyahiv i najbilshih paruvan za linijnij chas Gamiltoniv cikl mozhna znajti z pravilnogo intervalnogo grafu podannya za chas O n log n displaystyle O n log n ale yaksho graf ye vhidnim dlya zavdannya cyu zh zadachu mozhna rozv yazati za linijnij chas sho mozhna uzagalniti na intervalni grafi Zadacha en zalishayetsya NP povnoyu navit koli vona obmezhena indiferentnimi grafami Odnak vona ye en yaksho parametrizuvati za zagalnoyu kilkistyu koloriv na vhodi ZastosuvannyaU matematichnij psihologiyi indiferentni grafi vinikayut iz funkcij korisnosti masshtabuvannyam funkciyi tak sho odna odinicya predstavlyaye riznicyu korisnosti dosit maloyu tak sho dlya osobistosti odinicya mozhe vvazhatisya nesuttyevoyu U comu zastosuvanni pari elementiv korisnosti yakih dosit veliki mozhna chastkovo vporyadkuvati za vidnosnim poryadkom korisnosti sho daye en U bioinformatici zadachu dodavannya rozfarbovanogo grafu do pravilno rozfarbovanogo grafu odinichnih vidrizkiv mozhna vikoristati dlya modelyuvannya viyavlennya pomilkovo negativnih zbirok genomu DNK iz fragmentiv Div takozhPorogovij graf graf rebra yakogo viznachayutsya sumami mitok vershin a ne riznicyami mitok Trivialno doskonalij graf intervalnij graf dlya yakogo kozhna para intervaliv vkladena abo neperervana a ne nalezhnim chinom peretinayetsyaPrimitkiRoberts 1969 s 139 146 Bogart West 1999 s 21 23 Wegner 1967 Looges Olariu 1993 s 15 25 Jackowski 1992 s 103 109 Gutierrez Oubina 1996 s 199 205 Mertzios 2008 s 332 337 Brandstadt Hundt Mancini Wagner 2010 s 897 910 Cohen 1982 s 21 24 Kaplan Shamir 1996 s 540 561 Golumbic Rotics 1999 s 5 17 Lozin 2008 s 871 882 Bertossi 1983 s 97 101 Panda Das 2003 s 153 161 von Rimscha 1983 s 283 291 Bentley Stanat Williams 1977 s 209 212 Corneil Kim Natarajan Olariu Sprague 1995 s 99 104 Herrera de Figueiredo Meidanis Picinin de Mello 1995 s 179 184 Corneil 2004 s 371 379 Hell Huang 2004 s 554 570 Keil 1985 s 201 206 Ibarra 2009 s 1105 1108 Marx 2006 s 995 1002 Roberts 1970 s 243 258 Goldberg Golumbic Kaplan Shamir 2009 LiteraturaFred S Roberts Indifference graphs Proof Techniques in Graph Theory Proc Second Ann Arbor Graph Theory Conf Ann Arbor Mich 1968 Academic Press New York 1969 S 139 146 Kenneth P Bogart Douglas B West A short proof that proper unit 1999 T 201 vip 1 3 28 chervnya S 21 23 DOI 10 1016 S0012 365X 98 00310 0 Wegner G Eigenschaften der Nerven homologisch einfacher Familien im Rn Gottingen Germany Gottingen University 1967 Ph D thesis Yak procitovano v Hell Huang 2004 Peter J Looges Stephan Olariu Optimal greedy algorithms for indifference graphs Computers amp Mathematics with Applications 1993 T 25 vip 7 28 chervnya S 15 25 DOI 10 1016 0898 1221 93 90308 I Zygmunt Jackowski A new characterization of proper interval graphs 1992 T 105 vip 1 3 28 chervnya S 103 109 DOI 10 1016 0012 365X 92 90135 3 Gutierrez M Oubina L Metric characterizations of proper interval graphs and tree clique graphs Journal of Graph Theory 1996 T 21 vip 2 28 chervnya S 199 205 DOI 10 1002 SICI 1097 0118 199602 21 2 lt 199 AID JGT9 gt 3 0 CO 2 M George B Mertzios A matrix characterization of interval and proper interval graphs Applied Mathematics Letters 2008 T 21 vip 4 28 chervnya S 332 337 DOI 10 1016 j aml 2007 04 001 Andreas Brandstadt Christian Hundt Federico Mancini Peter Wagner Rooted directed path graphs are leaf powers Discrete Mathematics 2010 T 310 28 chervnya S 897 910 DOI 10 1016 j disc 2009 10 006 Joel E Cohen The asymptotic probability that a random graph is a unit interval graph indifference graph or proper interval graph 1982 T 40 vip 1 28 chervnya S 21 24 DOI 10 1016 0012 365X 82 90184 4 Haim Kaplan Ron Shamir Pathwidth bandwidth and completion problems to proper interval graphs with small cliques SIAM Journal on Computing 1996 T 25 vip 3 28 chervnya S 540 561 DOI 10 1137 S0097539793258143 Martin Charles Golumbic Udi Rotics The clique width of unit interval graphs is unbounded Proceedings of the Thirtieth Southeastern International Conference on Combinatorics Graph Theory and Computing Boca Raton FL 1999 1999 T 140 S 5 17 Congressus Numerantium Vadim V Lozin From tree width to clique width excluding a unit interval graph Algorithms and computation Springer Berlin 2008 T 5369 S 871 882 Lecture Notes in Comput Sci DOI 10 1007 978 3 540 92182 0 76 Alan A Bertossi Finding Hamiltonian circuits in proper interval graphs Information Processing Letters 1983 T 17 vip 2 28 chervnya S 97 101 DOI 10 1016 0020 0190 83 90078 9 Panda B S Das S K A linear time recognition algorithm for proper interval graphs Information Processing Letters 2003 T 87 vip 3 28 chervnya S 153 161 DOI 10 1016 S0020 0190 03 00298 9 Michael von Rimscha Reconstructibility and perfect graphs Discrete Mathematics 1983 T 47 vip 2 3 28 chervnya S 283 291 DOI 10 1016 0012 365X 83 90099 7 Jon L Bentley Donald F Stanat E Hollins Williams Jr The complexity of finding fixed radius near neighbors 1977 T 6 vip 6 28 chervnya S 209 212 DOI 10 1016 0020 0190 77 90070 9 Derek G Corneil Hiryoung Kim Sridhar Natarajan Stephan Olariu Alan P Sprague Simple linear time recognition of unit interval graphs Information Processing Letters 1995 T 55 vip 2 28 chervnya S 99 104 DOI 10 1016 0020 0190 95 00046 F Celina M Herrera de Figueiredo Joao Meidanis Celia Picinin de Mello A linear time algorithm for proper interval graph recognition Information Processing Letters 1995 T 56 vip 3 28 chervnya S 179 184 DOI 10 1016 0020 0190 95 00133 W Derek G Corneil A simple 3 sweep LBFS algorithm for the recognition of unit interval graphs Discrete Applied Mathematics 2004 T 138 vip 3 28 chervnya S 371 379 DOI 10 1016 j dam 2003 07 001 Pavol Hell Jing Huang Certifying LexBFS recognition algorithms for proper interval graphs and proper interval bigraphs SIAM Journal on Discrete Mathematics 2004 T 18 vip 3 28 chervnya S 554 570 DOI 10 1137 S0895480103430259 J Mark Keil Finding Hamiltonian circuits in interval graphs Information Processing Letters 1985 T 20 vip 4 28 chervnya S 201 206 DOI 10 1016 0020 0190 85 90050 X Louis Ibarra A simple algorithm to find Hamiltonian cycles in proper interval graphs Information Processing Letters 2009 T 109 vip 18 28 chervnya S 1105 1108 DOI 10 1016 j ipl 2009 07 010 Daniel Marx Precoloring extension on unit interval graphs Discrete Applied Mathematics 2006 T 154 vip 6 28 chervnya S 995 1002 DOI 10 1016 j dam 2005 10 008 Fred S Roberts On nontransitive indifference Journal of Mathematical Psychology 1970 T 7 28 chervnya S 243 258 DOI 10 1016 0022 2496 70 90047 7 Paul W Goldberg Martin C Golumbic Haim Kaplan Ron Shamir Four strikes against physical mapping of DNA Journal of Computational Biology 2009 T 2 vip 2 28 chervnya DOI 10 1089 cmb 1995 2 139 PMID 7497116 PosilannyaInformation System on Graph Class Inclusions 3 travnya 2021 u Wayback Machine unit interval graph 6 travnya 2021 u Wayback Machine

Дата публікації:
Топ