| Naslov: | Cover-incomparability graphs and chordal graphs |
|---|
| Avtorji: | ID Brešar, Boštjan (Avtor)
ID Changat, Manoj (Avtor)
ID Dravec, Tanja (Avtor)
ID Mathews, Joseph (Avtor)
ID Mathews, Antony (Avtor) |
|---|
| Datoteke: |  http://dx.doi.org/10.1016/j.dam.2010.07.001
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Delo ni kategorizirano |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | FNM - Fakulteta za naravoslovje in matematiko
|
|---|
| Opis: | Problem prepoznavanja grafov pokritij-neprimerljivosti (to je grafov, ki jih dobimo iz delno urejenih množic kot povezavno unijo njihovega grafa pokritij in grafa neprimerljivosti) je NP-poln v splošnem, kot so dokazali v [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26 (2009) 229-236], medtem ko je na primer očitno polinomski v razredu dreves. V tem članku se osredotočimo na razrede tetivnih grafov in dokažemo, da je vsak graf pokritij-neprimerljivosti, ki je tetiven graf, kar graf intervalov. Okarakteriziramo tiste delno urejene množice, ki imajo za graf pokritij-neprimerljivosti bločni graf, oziroma razcepljeni graf in tudi okarakteriziramo grafe pokritij-neprimerljivosti med bločnimi, oziroma razcepljenimi grafi. Slednji karakterizaciji dasta tudi linearen algoritem za prepoznavanje bločnih, oziroma razcepljenih grafov, ki so grafi pokritij-neprimerljivosti. |
|---|
| Ključne besede: | matematika, teorija grafov, delno urejena množica, temeljni graf, tetiven graf, razcepljen graf, bločni graf, mathematics, graph theory, poset, underlying graph, chordal graph, split graf, block graph |
|---|
| Leto izida: | 2010 |
|---|
| Št. strani: | str. 1752-1759 |
|---|
| Številčenje: | Vol. 158, iss. 16 |
|---|
| PID: | 20.500.12556/DKUM-51869  |
|---|
| UDK: | 519.17 |
|---|
| COBISS.SI-ID: | 15656537 |
|---|
| ISSN pri članku: | 0166-218X |
|---|
| NUK URN: | URN:SI:UM:DK:ETFEWXAE |
|---|
| Datum objave v DKUM: | 10.07.2015 |
|---|
| Število ogledov: | 1471 |
|---|
| Število prenosov: | 94 |
|---|
| Metapodatki: |    |
|---|
| Področja: | Ostalo
|
|---|
|
:
|
BREŠAR, Boštjan, CHANGAT, Manoj, DRAVEC, Tanja, MATHEWS, Joseph in MATHEWS, Antony, 2010, Cover-incomparability graphs and chordal graphs. Discrete applied mathematics [na spletu]. 2010. Vol. 158, no. 16, p. 1752–1759. [Dostopano 1 april 2025]. Pridobljeno s: http://dx.doi.org/10.1016/j.dam.2010.07.001
|
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
