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 (2)
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
This page was built for publication: Finding cut-vertices in the square roots of a graph