[PDF][PDF] Linear-time certifying recognition algorithms and forbidden induced subgraphs.
P Heggernes, D Kratsch - Nord. J. Comput., 2007 - ii.uib.no
We give the first linear-time certifying algorithms to recognize split graphs, threshold graphs,
chain graphs, co-chain graphs and trivially perfect graphs, with sublinear certificates for …
chain graphs, co-chain graphs and trivially perfect graphs, with sublinear certificates for …
[PDF][PDF] Graph modification problems related to graph classes
F Mancini - PhD degree dissertation, University of Bergen Norway, 2008 - Citeseer
This thesis consists of two parts. In the second part the research papers that constitute the
new results of the thesis are presented. In this first part we want to put these results in a …
new results of the thesis are presented. In this first part we want to put these results in a …
On the probe problem for (r, ℓ)-well-coveredness: algorithms and complexity
L Faria, US Souza - Theoretical Computer Science, 2022 - Elsevier
Let C be a class of graphs. A graph G=(V, E) is C-probe if V (G) can be partitioned into two
sets: non-probes N and probes P, where N is an independent set and new edges may be …
sets: non-probes N and probes P, where N is an independent set and new edges may be …
[HTML][HTML] On probe permutation graphs
DB Chandler, MS Chang, T Kloks, J Liu… - Discrete Applied …, 2009 - Elsevier
Given a class of graphs G, a graph G is a probe graph ofG if its vertices can be partitioned
into two sets, P, the probes, and an independent set N, the nonprobes, such that G can be …
into two sets, P, the probes, and an independent set N, the nonprobes, such that G can be …
Characterisations and linear-time recognition of probe cographs
VB Le, HN De Ridder - Graph-Theoretic Concepts in Computer Science …, 2007 - Springer
Cographs are those graphs without induced path on four vertices. A graph G is a probe
cograph if its vertex set can be partitioned into two sets, N (non-probes) and P (probes) …
cograph if its vertex set can be partitioned into two sets, N (non-probes) and P (probes) …
Probe threshold and probe trivially perfect graphs
D Bayer, HN de Ridder - Theoretical Computer Science, 2009 - Elsevier
An undirected graph G=(V, E) is a probeC graph if its vertex set can be partitioned into two
sets, N (nonprobes) and P (probes) where N is independent and there exists E′⊆ N× N …
sets, N (nonprobes) and P (probes) where N is independent and there exists E′⊆ N× N …
On the Probe Problem for -Well-Coveredness
L Faria, US Souza - International Computing and Combinatorics …, 2021 - Springer
Let CC be a class of graphs. A graph G=(V, E) G=(V, E) is CC–probe if V (G) can be
partitioned into two sets: non-probes NN and probes PP, where NN is an independent set …
partitioned into two sets: non-probes NN and probes PP, where NN is an independent set …
Recognition of probe cographs and partitioned probe distance hereditary graphs
DB Chandler, MS Chang, T Kloks, J Liu… - … Conference on Algorithmic …, 2006 - Springer
Given a class of graphs \calG, a graph G is a probe graph of \calG if its vertices can be
partitioned into two sets ℙ (the probes) and ℕ (nonprobes), where ℕ is an independent set …
partitioned into two sets ℙ (the probes) and ℕ (nonprobes), where ℕ is an independent set …
Partitioned probe comparability graphs
DB Chandler, MS Chang, T Kloks, J Liu… - Theoretical Computer …, 2008 - Elsevier
Given a class of graphs G, a graph G is a probe graph of G if its vertices can be partitioned
into a set of probes and an independent set of nonprobes such that G can be embedded into …
into a set of probes and an independent set of nonprobes such that G can be embedded into …
Probe split graphs
HN De Ridder - Discrete Mathematics and Theoretical Computer …, 2007 - inria.hal.science
An undirected graph G=(V, E) is a probe split graph if its vertex set can be partitioned into
two sets, N (non-probes) and P (probes) where N is independent and there exists E'⊆ N× N …
two sets, N (non-probes) and P (probes) where N is independent and there exists E'⊆ N× N …