Reconfiguration of cliques in a graph

DOI10.1016/J.DAM.2023.01.026MaRDI QIDQ2700609zbMATH OpenOpenAlexFDO

Authors Takehiro Ito, Hirotaka Ono, Yota Otachi

Publication date 27 April 2023

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2023.01.026

zbMATH Keywords

cliquecombinatorial reconfigurationgraph algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Reconfiguration of cliques in a graph
• Independent set reconfiguration in cographs
• Shortest Paths between Shortest Paths and Independent Sets
• Complexity of independent set reconfigurability problems
• Reconfiguration of Colorable Sets in Classes of Perfect Graphs

Cites work

• A c^k n 5-approximation algorithm for treewidth
• A Characterization of Comparability Graphs and of Interval Graphs
• A New Algorithm for Generating All the Maximal Independent Sets
• A partial k-arboretum of graphs with bounded treewidth
• Algorithmic graph theory and perfect graphs
• Complexity of independent set reconfigurability problems
• Efficient graph representations
• Graph Classes: A Survey
• Graph minors. II. Algorithmic aspects of tree-width
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 861332 (Why is no real title available?)
• Incidence matrices and interval graphs
• Independent set reconfiguration in cographs and their generalizations
• Introduction to reconfiguration
• Normal hypergraphs and the perfect graph conjecture
• On computing longest paths in small graph classes
• On graphs with polynomially solvable maximum-weight clique problem
• On the complexity of reconfiguration problems
• On the parameterized complexity of multiple-interval graph problems
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Parameterized complexity of graph constraint logic
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Reconfiguration in bounded bandwidth and tree-depth
• Reconfiguration of cliques in a graph
• Reconfiguration of vertex covers in a graph
• Reconfiguration over tree decompositions
• Reconfiguring independent sets in claw-free graphs
• Shortest Reconfiguration of Sliding Tokens on a Caterpillar
• Sliding tokens on a cactus
• Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs
• The complexity of change
• The complexity of independent set reconfiguration on bipartite graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Token jumping in minor-closed classes
• Token sliding on chordal graphs

Cited in

(11)

• Reconfiguration of cliques in a graph
• Reconfigurations in Graphs and Grids
• Reconfiguring multiple connected components with size multiset constraints
• Changing induced subgraph isomorphisms under extended reconfiguration rules
• Shortest paths on polymatroids and hypergraphic polytopes
• Changing induced subgraph isomorphisms under extended reconfiguration rules
• Independent set reconfiguration on directed graphs
• Biclique reconfiguration in bipartite graphs
• A note on reconfiguration graphs of cliques
• Reachability of independent sets and vertex covers under extended reconfiguration rules
• Token sliding independent set reconfiguration on block graphs

This page was built for publication: Reconfiguration of cliques in a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2700609)