H-colouring revisited
Чланак у часопису (Објављена верзија)
Метаподаци
Приказ свих података о документуАпстракт
In this paper we give a new, shortened proof of NP-completeness of CSP problem for undirected, non bipartite graphs, of interest for generalization to QCSP problem. We also give some illustrative examples.
Кључне речи:
H-colouring undirected graph / CSPИзвор:
Filomat, 2023, 8747-8754Издавач:
- Faculty of Sciences and Mathematics, Department of Mathematics
Колекције
Институција/група
GraFarTY - JOUR AU - Božin, Vladimir AU - Lazarević, Ivan PY - 2023 UR - https://grafar.grf.bg.ac.rs/handle/123456789/3485 AB - In this paper we give a new, shortened proof of NP-completeness of CSP problem for undirected, non bipartite graphs, of interest for generalization to QCSP problem. We also give some illustrative examples. PB - Faculty of Sciences and Mathematics, Department of Mathematics T2 - Filomat T1 - H-colouring revisited EP - 8754 SP - 8747 DO - 10.2298/FIL2326747B ER -
@article{ author = "Božin, Vladimir and Lazarević, Ivan", year = "2023", abstract = "In this paper we give a new, shortened proof of NP-completeness of CSP problem for undirected, non bipartite graphs, of interest for generalization to QCSP problem. We also give some illustrative examples.", publisher = "Faculty of Sciences and Mathematics, Department of Mathematics", journal = "Filomat", title = "H-colouring revisited", pages = "8754-8747", doi = "10.2298/FIL2326747B" }
Božin, V.,& Lazarević, I.. (2023). H-colouring revisited. in Filomat Faculty of Sciences and Mathematics, Department of Mathematics., 8747-8754. https://doi.org/10.2298/FIL2326747B
Božin V, Lazarević I. H-colouring revisited. in Filomat. 2023;:8747-8754. doi:10.2298/FIL2326747B .
Božin, Vladimir, Lazarević, Ivan, "H-colouring revisited" in Filomat (2023):8747-8754, https://doi.org/10.2298/FIL2326747B . .