Search
Filters
total: 590
filtered: 315
Search results for: color
-
The complexity of the T-coloring problem for graphs with small degree.
PublicationW pracy ustalono złożoność obliczeniową problemu optymalnego kolorowania grafów o ustalonym stopniu.
-
On the complexity of distributed graph coloring with local minimality constraints
PublicationArtykuł traktuje o zachłannym kolorowaniu grafów w modelu rozproszonym. Omówiono algorytmy rozproszone, dające w wyniku pokolorowanie spełniające warunki dla pokolorowań sekwencyjnych typu S oraz Largest-First (LF). Udowodniono również, że każda rozproszona implementacja algorytmu S wymaga co najmniej Omega(log n / log log n) rund, a algorytmu LF co najmniej Omega (n^{1/2}) rund, gdzie n oznacza liczbę wierzchołków grafu.
-
Edge coloring of graphs of signed class 1 and 2
PublicationRecently, Behr (2020) introduced a notion of the chromatic index of signed graphs and proved that for every signed graph (G, σ) it holds that ∆(G) ≤ χ′(G,σ) ≤ ∆(G) + 1, where ∆(G) is the maximum degree of G and χ′ denotes its chromatic index. In general, the chromatic index of (G, σ) depends on both the underlying graph G and the signature σ. In the paper we study graphs G for which χ′(G, σ) does not depend on σ. To this aim we...
-
Optimal backbone coloring of split graphs with matching backbones
PublicationFor a graph G with a given subgraph H, the backbone coloring is defined as the mapping c: V(G) -> N+ such that |c(u)-c(v)| >= 2 for each edge uv \in E(H) and |c(u)-c(v)| >= 1 for each edge uv \in E(G). The backbone chromatic number BBC(G;H) is the smallest integer k such that there exists a backbone coloring with max c(V(G)) = k. In this paper, we present the algorithm for the backbone coloring of split graphs with matching backbone.
-
Trypsin inhibitor, antioxidant and antimicrobial activities as well as chemical composition of potato sprouts originating from yellow- and colored-fleshed varieties
Publication -
Global variation in anastomosis and end colostomy formation following left‐sided colorectal resection
Publication -
A note on polynomial algorithm for cost coloring of bipartite graphs with Δ ≤ 4
PublicationIn the note we consider vertex coloring of a graph in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of coloring is the sum of costs incurred at each vertex. We show that the minimum cost coloring problem for n-vertex bipartite graph of degree ∆≤4 can be solved in O(n^2) time. This extends Jansen’s result [K.Jansen,The optimum cost chromatic partition problem, in:...
-
Sharp bounds for the complexity of semi-equitable coloring of cubic and subcubic graphs
PublicationIn this paper we consider the complexity of semi-equitable k-coloring of the vertices of a cubic or subcubic graph. We show that, given n-vertex subcubic graph G, a semi-equitable k-coloring of G is NP-hard if s >= 7n/20 and polynomially solvable if s <= 7n/21, where s is the size of maximum color class of the coloring.
-
Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs
PublicationWe consider the complexity of semi-equitable k-coloring, k>3, of the vertices of a cubic or subcubic graph G. In particular, we show that, given a n-vertex subcubic graph G, it is NP-complete to obtain a semi-equitable k-coloring of G whose non-equitable color class is of size s if s>n/3, and it is polynomially solvable if s, n/3.
-
Self-stabilizing algorithms for graph coloring with improved performance guarantees
PublicationW pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm kolorowania grafów oparty na konstrukcji drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm z gwarantowaną wielomianową liczbą ruchów, który dokładnie koloruje grafy dwudzielne.
-
Equitable 4-coloring of cacti and edge-cacti in polynomial time
PublicationRozważono problem wyznaczania sprawiedliwej liczby chromatycznej kaktusów i drzew wielokątowych bez trójkątów i krawędzi wiszących. Podano wielomianowy algorytm wyznaczający pokolorowanie optymalne, oparty na paradygmacie programowania dynamicznego. Tym samym znaleziona została kolejna klasa grafów planarnych, dla której kolorowanie sprawiedliwe jawi się jako zagadnienie obliczeniowo łatwe.
-
A 27/26-approximation algorithm for the chromatic sum coloring of bipartitegraphs
PublicationWe consider the CHROMATIC SUM PROBLEM on bipartite graphs which appears to be much harder than the classical CHROMATIC NUMBER PROBLEM. We prove that the CHROMATIC SUM PROBLEM is NP-complete on planar bipartite graphs with Delta less than or equal to 5, but polynomial on bipartite graphs with Delta less than or equal to 3, for which we construct an O(n(2))-time algorithm. Hence, we tighten the borderline of intractability for this...
-
Interval Edge Coloring of Bipartite Graphs with Small Vertex Degrees
PublicationAn edge coloring of a graph G is called interval edge coloring if for each v ∈ V(G) the set of colors on edges incident to v forms an interval of integers. A graph G is interval colorable if there is an interval coloring of G. For an interval colorable graph G, by the interval chromatic index of G, denoted by χ'_i(G), we mean the smallest number k such that G is interval colorable with k colors. A bipartite graph G is called (α,β)-biregular...
-
Phenol-rich alternatives for Rosa x damascena Mill. Efficient phytochemical profiling using different extraction methods and colorimetric assays
Publication -
Urinary 5-hydroxymethyluracil and 8-oxo-7,8-dihydroguanine as potential biomarkers in patients with colorectal cancer
Publication -
The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones
PublicationGiven a graph G, a spanning subgraph H of G and an integer λ>=2, a λ-backbone coloring of G with backbone H is a vertex coloring of G using colors 1, 2, ..., in which the color difference between vertices adjacent in H is greater than or equal to lambda. The backbone coloring problem is to find such a coloring with maximum color that does not exceed a given limit k. In this paper, we study the backbone coloring problem for bounded-degree...
-
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
Publication -
Efficient List Cost Coloring of Vertices and∕or Edges of Some Sparse Graphs
Publication -
Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms
Publication -
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
PublicationW artykule rozważamy listowo-kosztowe kolorowanie wierzchołków i krawędzi grafu w modelu wierzchołkowym, krawędziowym, totalnym i pseudototalnym. Stosujemy programowanie dynamiczne w celu otrzymania algorytmów wielomianowych dla drzew. Następnie uogólniamy to podejście na dowolne grafy z ograniczonymi liczbami cyklomatycznymi i na ich multikolorowania.
-
Scheduling with precedence constraints: mixed graph coloring in series-parallel graphs.
PublicationW pracy rozważono problem kolorowania grafów mieszanych, opisujący zagadnienie szeregowania zadań, w którym zależności czasowe zadań mają charakter częściowego porządku lub wzajemnego wykluczania. Dla przypadku, w którym graf zależności jest szeregowo-równoległy, podano algorytm rozwiązujący problem optymalnie w czasie $O(n^3.376 * log n)$.
-
Computer experiments with a parallel clonal selection algorithm for the graph coloring problem
PublicationArtificial immune systems (AIS) are algorithms that are based on the structure and mechanisms of the vertebrate immune system. Clonal selection is a process that allows lymphocytes to launch a quick response to known pathogens and to adapt to new, previously unencountered ones. This paper presents a parallel island model algorithm based on the clonal selection principles for solving the Graph Coloring Problem. The performance of...
-
Efficient list cost coloring of vertices and/or edges of some sparse graphs
PublicationRozważane jest kolorowanie wierzchołków i krawędzi grafów w modelach klasycznym, totalnym i pseudototalnym z uwzględnieniem dodatkowego ograniczenia w postaci list dostępnych kolorów. Proponujemy wielomianowy algorytm oparty na paradygmacie programowania dynamicznego dla grafów o strukturze drzewa. Wynik ten można uogólnić na grafy o liczbie cyklomatycznej ograniczonej z góry przez dowolnie wybraną stała.
-
On Optimal Backbone Coloring of Split and Threshold Graphs with Pairwise Disjoint Stars
Publication -
Equitable coloring of graphs. Recent theoretical results and new practical algorithms
PublicationIn this paper we survey recent theoretical results concerning conditions for equitable colorability of some graphs and recent theoretical results concerning the complexity of equitable coloring problem. Next, since the general coloring problem is strongly NP-hard, we report on practical experiments with some efficient polynomial-time algorithms for approximate equitable coloring of general graphs.
-
The computational complexity of the backbone coloring problem for planar graphs with connected backbones
PublicationIn the paper we study the computational complexity of the backbone coloring problem for planar graphs with connected backbones. For every possible value of integer parameters λ≥2 and k≥1 we show that the following problem: Instance: A simple planar graph GG, its connected spanning subgraph (backbone) HH. Question: Is there a λ-backbone coloring c of G with backbone H such that maxc(V(G))≤k? is either NP-complete or polynomially...
-
Anticancer potential of acetone extracts from selected Potentilla species against human colorectal cancer cells
Publication -
Multispectral Imaging Using Fluorescent Properties of Indocyanine Green and Methylene Blue in Colorectal Surgery—Initial Experience
PublicationIntroduction: Image-guided surgery is becoming a new tool in colorectal surgery. Intraoperative visualisation of different structures using fluorophores helps during various steps of operations. In our report, we used two fluorophores—indocyanine green (ICG), and methylene blue (MB)— during different steps of colorectal surgery, using one camera system for two separate near-infrared wavelengths. Material and methods: Twelve patients...
-
Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
Publication -
A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints
PublicationWe address a generalization of the classical 1- and 2-processor unit execution time scheduling problem on dedicated machines. In our chromatic model of scheduling machines have non-simultaneous availability times and tasks have arbitrary release times and due dates. Also, the versatility of our approach makes it possible to generalize all known classical criteria of optimality. Under these stipulations we show that the problem...
-
Consensus models: Computational complexity aspects in modern approaches to the list coloring problem
PublicationArtykuł poświęcony jest nowym modelom konsensusowego kolorowania grafów. Artykuł zawiera omówienie trzech takich modeli, analizę ich złożoności obliczeniowej oraz wielomianowy algorytm dla częściowych k-drzew, dla tzw. modelu addytywnego.
-
A note on fast approximate backbone coloring of split graphs with star--like backbones
PublicationDla grafu G = (V, E) z wyróżnionym podgrafem H, kolorowanie szkieletowe jest zdefiniowane jako odwzorowanie c spełniające |c(u) - c(v)| > 1 dla każdej krawędzi z E(H) oraz |c(u) - c(v)| > 0 dla każdej krawędzi z E(G). W pracy przedstawiono 1-przybliżony algorytm kolorowania szkieletowego split grafów ze skojarzeniem w szkielecie o złożoności O(|V|) oraz 1-przybliżony algorytm dla split grafów z rozłącznymi gwiazdami w szkielecie.
-
Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
PublicationIn the paper we consider the problems of equitable and semi-equitable coloring of vertices of cubic graphs. We show that in contrast to the equitable coloring, which is easy, the problem of semi-equitable coloring is NP- complete within a broad spectrum of graph parameters. This affects the complexity of batch scheduling of unit-length jobs with cubic incompatibility graph on three uniform processors to minimize...
-
Critical perspectives on media architecture: is it still possible to design projects without negatively affecting urban nighttime environments and will the future remain dynamic, bright and multi-colored?
PublicationNowadays, due to advances in electrical devices, new digital media, lighting, information and communication technologies, cities are being used 24/7. The paper discusses critical aspects of Media Architecture in the context of public spaces as well as urban nighttime environments from the perspective of a practising lighting architect. The author examines recent issues of negative design approaches and presents proposals for improving...
-
Method-Dependent Epidemiological Cutoff Values for Detection of Triazole Resistance in Candida and Aspergillus Species for the Sensititre YeastOne Colorimetric Broth and Etest Agar Diffusion Methods
PublicationAlthough the Sensititre Yeast-One (SYO) and Etest methods are widely utilized, interpretive criteria are not available for triazole susceptibility testing of Candida or Aspergillus species. We collected fluconazole, itraconazole, posaconazole, and voriconazole SYO and Etest MICs from 39 laboratories representing all continents for (method/agent-dependent) 11,171 Candida albicans, 215 C. dubliniensis, 4,418 C. glabrata species complex,...
-
Incredible Clinical Causes Beyond A Five-Month-Old Boy's Poor Feeding Include His Rapid Brain Cognition And Preference For Certain Colors: Case Report
Publication -
Identification of High-Risk Stage II Colorectal Tumors by Combined Analysis of the NDRG1 Gene Expression and the Depth of Tumor Invasion
Publication -
Changes in subcellular localization of visfatin in human colorectal HCT-116 carcinoma cell line after cytochalasin B treatment
Publication -
Ultrasound and Clinical Preoperative Characteristics for Discrimination Between Ovarian Metastatic Colorectal Cancer and Primary Ovarian Cancer: A Case-Control Study
PublicationThe aim of this study was to describe the clinical and sonographic features of ovarian metastases originating from colorectal cancer (mCRC), and to discriminate mCRC from primary ovarian cancer (OC). We conducted a multi-institutional, retrospective study of consecutive patients with ovarian mCRC who had undergone ultrasound examination using the International Ovarian Tumor Analysis (IOTA) terminology, with the addition of evaluating...
-
Comparison of peptide cancer signatures identified by mass spectrometry in serum of patients with head and neck, lung and colorectal cancers: Association with tumor progression
Publication -
Urinary Measurement of Epigenetic DNA Modifications: A Non-Invasive Assessment of the Whole-Body Epigenetic Status in Healthy Subjects and Colorectal Cancer Patients
Publication -
Association between use of enhanced recovery after surgery protocols and postoperative complications in colorectal surgery in Europe: The EuroPOWER international observational study
Publication -
Red Kale (Brassica oleracea L. ssp. acephala L. var. sabellica) Induces Apoptosis in Human Colorectal Cancer Cells In Vitro
PublicationThis article presents the results of studies investigating the effect of red kale (Brassica oleracea L. ssp. acephala L. var. sabellica) extract on cancer cells (HT-29). The cytotoxicity of the red kale extract was assessed using MTT and LDH assays, while qRT-PCR was employed to analyze the expression of genes associated with the p53 signaling pathway to elucidate the effect of the extract on cancer cells. Furthermore, HPLC-ESI-QTOF-MS/MS...
-
Antiproliferative, Antiangiogenic, and Antimetastatic Therapy Response by Mangiferin in a Syngeneic Immunocompetent Colorectal Cancer Mouse Model Involves Changes in Mitochondrial Energy Metabolism
PublicationIn spite of the current advances and achievements in cancer treatments, colorectal cancer (CRC) persists as one of the most prevalent and deadly tumor types in both men and women worldwide. Drug resistance, adverse side effects and high rate of angiogenesis, metastasis and tumor relapse remain one of the greatest challenges in long-term management of CRC and urges need for new leads of anticancer drugs. We demonstrate that CRC...
-
c-Myc Protein Level Affected by Unsymmetrical Bisacridines Influences Apoptosis and Senescence Induced in HCT116 Colorectal and H460 Lung Cancer Cells
PublicationUnsymmetrical bisacridines (UAs) are highly active antitumor compounds. They contain in their structure the drugs previously synthesized in our Department: C-1311 and C-1748. UAs exhibit different properties than their monomer components. They do not intercalate to dsDNA but stabilize the G-quadruplex structures, particularly those of the MYC and KRAS genes. Since MYC and KRAS are often mutated and constitutively expressed in cancer...
-
In vivo evidence of ascorbate involvement in the generation of epigenetic DNA modifications in leukocytes from patients with colorectal carcinoma, benign adenoma and inflammatory bowel disease
Publication -
Relationship between copper(ii) complexes with FomA adhesin fragments ofF. nucleatumand colorectal cancer. Coordination pattern and ability to promote ROS production
Publication -
Non-disjoint Decomposition Using r-admissibility and Graph Coloring and Its Application in Index Generation Functions Minimization
Publication -
Colorectal neuroendocrine neoplasms — update of the diagnostic and therapeutic guidelines (recommended by the Polish Network of Neuroendocrine Tumours) [Nowotwory neuroendokrynne jelita grubego — uaktualnione zasady diagnostyki i leczenia (rekomendowane przez Polską Sieć Guzów Neuroendokrynych)]
Publication -
The Effect of Steaming Beech, Birch and Maple Woods on Qualitative Indicators of the Surface
PublicationThis work presents the effect of steaming beech, birch and maple woods on the resulting quality of the milled wood surface. The steaming process of the studied woods results in a targeted change in the color of the wood, which changes from the original light white-gray color to fine reddishbrown to dark brown color shades that are more or less saturated depending on the temperature of the saturated water steam. The color changes...