Finding cut-vertices in the square roots of a graph
From MaRDI portal
Publication:5915963
DOI10.1016/j.dam.2018.10.028zbMath1406.05101OpenAlexW2901284861WikidataQ128943652 ScholiaQ128943652MaRDI QIDQ5915963
Publication date: 11 March 2019
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2018.10.028
cut-verticescactus-block graphsclique-separator decompositioncycle-power graphssquare root of a graph
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Graph operations (line graphs, products, etc.) (05C76)
Related Items
Graph square roots of small distance from degree one graphs, Parameterized leaf power recognition via embedding into graph products
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterized algorithms for finding square roots
- Characterizing width two for variants of treewidth
- Organizing the atoms of the clique separator decomposition into an atom tree
- Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs
- Powers of cycles, powers of paths, and distance graphs
- Uniqueness of graph square roots of girth six
- Finding cactus roots in polynomial time
- A game of cops and robbers
- Minimal triangulations of graphs: a survey
- The square of a block graph
- Decomposition by clique separators
- Connected cutsets of a graph and triangle bases of the cycle space
- A partial k-arboretum of graphs with bounded treewidth
- Computing roots of graphs is hard
- Characterizations and algorithmic applications of chordal graph embeddings
- Coloring the square of a \(K_{4}\)-minor free graph
- Algorithmic graph theory and perfect graphs
- A good characterization of squares of strongly chordal split graphs
- Optimal decomposition by clique separators
- A linear kernel for finding square roots of almost planar graphs
- Complexity of finding graph roots with girth conditions
- Square roots of minor closed graph classes
- Computing square roots of trivially perfect and threshold graphs
- A bound on the chromatic number of the square of a planar graph
- The square of every two-connected graph is Hamiltonian
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Treewidth and Minimum Fill-in: Grouping the Minimal Separators
- 2-Distance Coloring of Sparse Graphs
- Bipartite roots of graphs
- Graph minors. II. Algorithmic aspects of tree-width
- Stability in circular arc graphs
- On the tree representation of chordal graphs
- Coloring Powers of Planar Graphs
- Revisiting Decomposition by Clique Separators
- Recognizing Powers of Proper Interval, Split, and Chordal Graphs
- Algorithms for Square Roots of Graphs
- A criterion for planarity of the square of a graph
- The square root of a graph
- Characterizing circular-arc graphs
- Linear-Time Algorithms for Tree Root Problems
- On \(H\)-topological intersection graphs
- Finding cut-vertices in the square roots of a graph
