Graph puzzles, homotopy, and the alternating group

DOI10.1016/0095-8956(74)90098-7zbMath0285.05110OpenAlexW2048036606WikidataQ56269533 ScholiaQ56269533MaRDI QIDQ1844853

Publication date: 1974

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(74)90098-7

Mathematics Subject Classification ID

Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Related Items (51)

Multi-agent Pathfinding with n Agents on Graphs with n Vertices: Combinatorial Classification and Tight Algorithmic Bounds ⋮ Best subset selection via a modern optimization lens ⋮ Motions of a connected subgraph representing a swarm of robots inside a graph of work stations ⋮ A linear time algorithm for the feasibility of pebble motion on trees ⋮ On the asymmetric generalizations of two extremal questions on friends-and-strangers graphs ⋮ Sliding piece puzzles with oriented tiles ⋮ On the state liveness of some classes of guidepath-based transport systems and its computational complexity ⋮ Sequentially Swapping Colored Tokens on Graphs ⋮ Polynomial-time optimal liveness enforcement for guidepath-based transport systems ⋮ A characterization of biconnected graphs reachable by robots jumping over \(m\) obstacles ⋮ Connectedness of friends-and-strangers graphs of complete bipartite graphs and others ⋮ The connectedness of the friends-and-strangers graph of a lollipop and others ⋮ Token Swapping on Trees ⋮ Time-expanded graph-based propositional encodings for makespan-optimal solving of cooperative path finding problems ⋮ The 5-puzzle doubly covers the soccer ball ⋮ Reconfiguration of connected graph partitions ⋮ Friends and strangers walking on graphs ⋮ Colored pebble motion on graphs ⋮ The maximal subgroups and the complexity of the flow semigroup of finite (di)graphs ⋮ Connectivity of old and new models of friends-and-strangers graphs ⋮ The direct power of a 1-graph ⋮ Multi-color pebble motion on graphs ⋮ Sequentially Swapping Colored Tokens on Graphs ⋮ Motion planning in Cartesian product graphs ⋮ Bayesian model averaging: A tutorial. (with comments and a rejoinder). ⋮ The kissing problem: how to end a gathering when everyone kisses everyone else goodbye ⋮ Cyclic shift problems on graphs ⋮ Configuration spaces of squares in a rectangle ⋮ Model uncertainty ⋮ Feasibility of motion planning on acyclic and strongly connected directed graphs ⋮ Sliding puzzles and rotating puzzles on graphs ⋮ On reachability in graphs with obstacles ⋮ Complexity of token swapping and its variants ⋮ When do stepwise algorithms meet subset selection criteria? ⋮ Pebble exchange group of graphs ⋮ Efficient generation of performance bounds for a class of traffic scheduling problems ⋮ Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch ⋮ Unnamed Item ⋮ Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard ⋮ Friends and strangers walking on graphs ⋮ Structural aspects of semigroups based on digraphs ⋮ Introduction to reconfiguration ⋮ Colored Pebble Motion on Graphs (Extended Abstract) ⋮ Fast Sequential and Parallel Vertex Relabelings of K_m,m ⋮ Pebble exchange on graphs ⋮ Typical and extremal aspects of friends-and-strangers graphs ⋮ Optimal pebble motion on a tree ⋮ Subdimensional expansion for multirobot path planning ⋮ On simulation in automata networks ⋮ Heuristics as Markov chains ⋮ Connectivity of friends-and-strangers graphs on random pairs

Cites Work

This page was built for publication: Graph puzzles, homotopy, and the alternating group