Ograniczanie wyników
Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 1

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote A Generalization of Join and an Algorithmic Recognition Problem
EN
We consider a new graph operation c2-join which generalizes join and co-join. We show that odd hole-free graphs (odd antihole-free graphs) are closed under c2-join and describe a polynomial time algorithm to recognize graphs that admit a c2-join. The time complexity of the (a) recognition problem, (b) maximum weight independent set (MWIS) problem, and (c) minimum coloring (MC) problem for odd hole-free graphs are still unknown. Let H be an odd hole-free graph that contains an odd antihole as an induced subgraph and GH be the class of all graphs generated from the induced subgraphs of H by using c2-join recursively. Then GH is odd hole-free, contains all P4-free graphs, complement of all bipartite graphs, and some imperfect graphs. We show that the MWIS problem, maximum weight clique (MWC) problem, MC problem, and minimum clique cover (MCC) problem can be solved efficiently for GH.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.