Back to Search
Start Over
Sandwich problem for [formula omitted]- and [formula omitted]-free multigraphs and its applications to positional games.
- Source :
-
Discrete Mathematics . Dec2015, Vol. 338 Issue 12, p2421-2436. 16p. - Publication Year :
- 2015
-
Abstract
- An n - multigraph G = ( V ; E i ∣ i ∈ I ) is a complete graph G = ( V , E ) whose edges are covered by n = | I | sets, E = ∪ i ∈ I E i , some of which might be empty. If this cover is a partition, then G is called an n - graph . We say that an n -graph G ′ = ( V ; E i ′ ∣ i ∈ I ) is an edge subgraph of an n -multigraph G = ( V ; E i ∣ i ∈ I ) if E i ′ ⊆ E i for all i ∈ I . We denote by Δ the n -graph on three vertices with three nonempty sets each containing a single edge, and by Π the four-vertex n -graph with two non-empty sets each of which contains the edges of a P 4 . In this paper, we recognize in polynomial time whether a given n -multigraph G contains a Π - and Δ -free n -subgraph, or not, and if yes, provide a polynomial delay algorithm generating all such subgraphs. The above decision problem can be viewed as a generalization of the sandwich problem for P 4 -free graphs solved by Golumbic et al. (1995). As a motivation and application, we consider the n -person positional game forms, which are known to be in a one-to-one correspondence with the Π - and Δ -free n -graphs. Given a game form g , making use of the above result, we recognize in polynomial time whether g is a subform of a positional (that is, tight and rectangular) game form and, if yes, we generate with polynomial delay all such positional extensions of g . [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 338
- Issue :
- 12
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 108613460
- Full Text :
- https://doi.org/10.1016/j.disc.2015.06.010