Attenzione: i dati modificati non sono ancora stati salvati. Per confermare inserimenti o cancellazioni di voci è necessario confermare con il tasto SALVA/INSERISCI in fondo alla pagina
IRIS
A mixed hypergraph is a pair H=(V; E U A), where V is the vertex set and E(A) the edge (the co-edge) set of H. A legal colouring of H gives the same (di0erent) colour(s) to at least two vertices of any co-edge (of any edge). The upper chromatic number of H is the maximum number x(H) of colours that can be used in a legal colouring. After giving a general upper bound to x(H), we here consider the co-hypergraph S=(X; 0 U T), where T is a (v3; b2)- configuration T over X . We prove that computing x(S) is NP-hard, but there exists a polynomial-time algorithm returning a colouring with 5/6 x(S) colours. We also provide an example showing that this approximation factor is tight.
On the upper chromatic number of (v3,b2)-configurations
A mixed hypergraph is a pair H=(V; E U A), where V is the vertex set and E(A) the edge (the co-edge) set of H. A legal colouring of H gives the same (di0erent) colour(s) to at least two vertices of any co-edge (of any edge). The upper chromatic number of H is the maximum number x(H) of colours that can be used in a legal colouring. After giving a general upper bound to x(H), we here consider the co-hypergraph S=(X; 0 U T), where T is a (v3; b2)- configuration T over X . We prove that computing x(S) is NP-hard, but there exists a polynomial-time algorithm returning a colouring with 5/6 x(S) colours. We also provide an example showing that this approximation factor is tight.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.12571/2153
Citazioni
ND
1
1
social impact
simulazione ASN
Il report seguente simula gli indicatori relativi alla propria produzione scientifica in relazione alle soglie ASN 2021-2023 del proprio SC/SSD. Si ricorda che il superamento dei valori soglia (almeno 2 su 3) è requisito necessario ma non sufficiente al conseguimento dell'abilitazione. La simulazione si basa sui dati IRIS e sugli indicatori bibliometrici alla data indicata e non tiene conto di eventuali periodi di congedo obbligatorio, che in sede di domanda ASN danno diritto a incrementi percentuali dei valori. La simulazione può differire dall'esito di un’eventuale domanda ASN sia per errori di catalogazione e/o dati mancanti in IRIS, sia per la variabilità dei dati bibliometrici nel tempo. Si consideri che Anvur calcola i valori degli indicatori all'ultima data utile per la presentazione delle domande.
La presente simulazione è stata realizzata sulla base delle specifiche raccolte sul tavolo ER del Focus Group IRIS coordinato dall’Università di Modena e Reggio Emilia e delle regole riportate nel DM 589/2018 e allegata Tabella A. Cineca, l’Università di Modena e Reggio Emilia e il Focus Group IRIS non si assumono alcuna responsabilità in merito all’uso che il diretto interessato o terzi faranno della simulazione. Si specifica inoltre che la simulazione contiene calcoli effettuati con dati e algoritmi di pubblico dominio e deve quindi essere considerata come un mero ausilio al calcolo svolgibile manualmente o con strumenti equivalenti.