×

Partitioned probe comparability graphs. (In honor of Prof. Dr. J. H. van Lint). (English) Zbl 1167.05323

Fomin, Fedor V. (ed.), Graph-theoretic concepts in computer science. 32nd international workshop, WG 2006, Bergen, Norway, June 22–24, 2006. Revised papers. Berlin: Springer (ISBN 978-3-540-48381-6/pbk). Lecture Notes in Computer Science 4271, 179-190 (2006).
Summary: Given a class of graphs \(\mathcal{G}\), a graph \(G\) is a probe graph of \(\mathcal{G}\) if its vertices can be partitioned into a set \(\mathbb P\) of probes and an independent set \(\mathbb N\) of nonprobes such that \(G\) can be embedded into a graph of \(\mathcal{G}\) by adding edges between certain nonprobes. If the partition of the vertices is a part of the input we call \(G\) a partitioned probe graph of \(\mathcal{G}\). In this paper we show that there exists a polynomial-time algorithm for the recognition of partitioned probe graphs of comparability graphs. This immediately leads to a polynomial-time algorithm for the recognition of partitioned probe graphs of cocomparability graphs. We then show that a partitioned graph \(G=(\mathbb{P}+\mathbb{N},E)\) is a partitioned probe permutation graph if and only if \(G\) is at the same time a partitioned probe graph of comparability and cocomparability graphs.
For the entire collection see [Zbl 1137.68005].

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity

Biographic References:

van Lint, J. H.
PDFBibTeX XMLCite
Full Text: DOI