| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava
Prva stran > Izpis gradiva

Izpis gradiva Pomoč

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:URL 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 Novo okno
UDK:519.17
COBISS.SI-ID:15656537 Novo okno
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:XML DC-XML DC-RDF
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 28 marec 2025]. Pridobljeno s: http://dx.doi.org/10.1016/j.dam.2010.07.001
Kopiraj citat
  
Skupna ocena:
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:Bookmark and Share


Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:Discrete applied mathematics
Skrajšan naslov:Discrete appl. math.
Založnik:Elsevier
ISSN:0166-218X
COBISS.SI-ID:25342464 Novo okno

Sekundarni jezik

Jezik:Neznan jezik
Naslov:Grafi pokritij-neprimerljivosti in tetivni grafi
Opis:The problem of recognizing cover-incomparability graphs (i.e. the graphs obtained from posets as the edge-union of their covering and incomparability graph) was shown to be NP-complete in general [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26 (2009) 229-236], while it is for instance clearly polynomial within trees. In this paper we concentrate on (classes of) chordal graphs, and show that any cover-incomparability graph that is a chordal graph is an interval graph. We characterize the posets whose cover-incomparability graph is a block graph, and a split graph, respectively, and also characterize the cover-incomparability graphs among block and split graphs, respectively. The latter characterizations yield linear time algorithms for the recognition of block and split graphs, respectively, that are cover-incomparability graphs.


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici