Finding cut-vertices in the square roots of a graph

DOI10.1016/j.dam.2018.10.028zbMath1406.05101OpenAlexW2901284861WikidataQ128943652 ScholiaQ128943652MaRDI QIDQ5915963

Guillaume Ducoffe

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

zbMATH Keywords

cut-verticescactus-block graphsclique-separator decompositioncycle-power graphssquare root of a graph

Mathematics Subject Classification ID

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

• Algorithm 447

Cites Work

• Unnamed Item
• 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
• 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