On the Complexity of Finding a Sun in a Graph [PDF]
, 2010 The sun is the graph obtained from a cycle of length even and at least six by adding edges to make the even-indexed vertices pairwise adjacent. Suns play an important role in the study of strongly chordal graphs. A graph is chordal if it does not contain
Hoàng, Chính T.
core +2 more sources
Complexity of Hamiltonian Cycle Reconfiguration
Algorithms, 2018 The Hamiltonian cycle reconfiguration problem asks, given two Hamiltonian cycles C 0 and C t of a graph G, whether there is a sequence of Hamiltonian cycles C 0 , C 1 , … , C t such that C i can be obtained ...
Asahi Takaoka
doaj +1 more source
The Dilworth Number of Auto-Chordal-Bipartite Graphs [PDF]
, 2013 The mirror (or bipartite complement) mir(B) of a bipartite graph B=(X,Y,E) has the same color classes X and Y as B, and two vertices x in X and y in Y are adjacent in mir(B) if and only if xy is not in E. A bipartite graph is chordal bipartite if none of
Berry, Anne +2 more
core +1 more source
On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
Theoretical Computer Science, 2007 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
C. M. Figueiredo +3 more
semanticscholar +3 more sources
Strongly chordal and chordal bipartite graphs are sandwich monotone
Journal of Combinatorial Optimization, 2009 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Heggernes, Pinar +3 more
openaire +3 more sources
Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
Discrete Mathematics, 1991 A set of vertices in a graph is called a dominating set if every vertex not in the set is adjacent to at least one vertex in the set. A dominating clique is a dominating set that induces a complete subgraph. The problem of locating a dominating clique of minimum cardinality is known to be NP-complete for general chordal graphs.
D. Kratsch
semanticscholar +2 more sources
Domination, independent domination, and duality in strongly chordal graphs
Discrete Applied Mathematics, 1984 Polynomial-time algorithms for finding minimum weight dominating sets and independent dominating sets in strongly chordal graphs are presented in this paper. The algorithms are based on linear programming formulations of the problems and consist of two stages: in the first - a greedy algorithm is used to solve the corresponding dual program, and in the
M. Farber
semanticscholar +2 more sources
Characterizing and computing the structure of clique intersections in strongly chordal graphs
Discrete Applied Mathematics, 2013 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Ragnar Nevries, Christian Rosenke
semanticscholar +2 more sources
Chordal- (k,ℓ)and strongly chordal- (k,ℓ)graph sandwich problems [PDF]
Journal of the Brazilian Computer Society, 2014 In this work, we consider the graph sandwich decision problem for property Π, introduced by Golumbic, Kaplan and Shamir: given two graphs G1=(V,E1) and G2=(V,E2), the question is to know whether there exists a graph G=(V,E) such that E1⊆E⊆E2 and G satisfies property Π. Particurlarly, we are interested in fully classifying the complexity of this problem
Couto, Fernanda +2 more
openaire +1 more source
Markov models for fMRI correlation structure: is brain functional connectivity small world, or decomposable into networks? [PDF]
, 2012 Correlations in the signal observed via functional Magnetic Resonance Imaging (fMRI), are expected to reveal the interactions in the underlying neural populations through hemodynamic response.
A. Gramfort +73 more
core +7 more sources