login
| EN

Izbrane teme o grafih, hipergrafih in Boolovih funkcijah / Selected topics on graphs, hypergraphs, and Boolean functions

Naziv

Tittle

Izbrane teme o grafih, hipergrafih in Boolovih funkcijah / Selected topics on graphs, hypergraphs, and Boolean functions

Akronim

Acronim

BI-US/24-26-088

Opis

Description

(SI) Projekt se osredotoča na dve glavni smeri raziskovanja, ki povezujeta grafe in hipergrafe ter delno tudi Boolove funkcije. Prva linija raziskovanja je povezana z raziskavami 3-uniformnih hipergrafov. Izhodišče je dobro znan odprt problem v zvezi z obstojem 'popolnoma kombinatornega' polinomskega časovnega algoritma za prepoznavanje pragovnih hipergrafov (ali, kar je enakovredno, pragovnih monotonih Boolovih funkcij, podanih s popolno DNO). Druga linija raziskav se ukvarja s konceptom v teoriji grafov, imenovanim klično dualno konformni grafi. Ta koncept je tesno povezan z dualno konformnimi hipergrafi, pojmom, uvedenim v prejšnjem bilateralnem sodelovanju med projektnima skupinama. Na podlagi začetnih rezultatov za razred KDK grafov je cilj v tem delu projekta raziskati nadaljnje strukturne in algoritmične lastnosti KDK grafov ter tovrstne grafe karakterizirati v posebnih primerih.

(EN) The project focuses on two main lines of research connecting graphs and hypergraphs, and partly also Boolean functions. The first line of research is related to investigations of 3-uniform hypergraphs. The second line of research deals with a concept in graph theory called clique dually conformal graphs. Motivated by these initial observations of the class of CDC graphs, the project goal in this part is to investigate further structural and algorithmic properties of CDC graphs, and characterize them in special cases.


Trajanje

Duration

01/07/2024 - 30/06/2026

Vodja projekta

Project Leader

Martin Milanič

Sodelujoče organizacije

Participating organizations

Rutgers University

Oddelek

Department

Oddelek za matematiko IAM
Univerza na Primorskem

Inštitut Andrej Marušič
UP IAM

Muzejski trg 2
6000 Koper
Slovenija

tel.: +386 (0)5 611 75 91
fax.: +386 (0)5 611 75 92
e-mail: info@iam.upr.si
Avtorske pravice
Izjava o dostopnosti