Complexity issues in switching of graphs

DOI10.1007/978-3-540-46464-8_5MaRDI QIDQ4502805zbMATH OpenFDO

Authors Andrzej Ehrenfeucht, Jurriaan Hage, Tero Harju, Grzegorz Rozenberg

Publication date 12 September 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-46464-8_5

zbMATH Keywords

graph transformationsswitching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The embedding problem for switching classes of graphs
• On the hardness of switching to a small number of edges
• Complexity of hypergraph coloring and Seidel's switching.
• scientific article; zbMATH DE number 125469
• Switching to hedgehog-free graphs is NP-complete

Cites work

• Biased graphs. I: Bias, balance, and gains
• Dynamic labeled 2-structures
• Graph theory with applications
• scientific article; zbMATH DE number 4006288 (Why is no real title available?)
• scientific article; zbMATH DE number 125469 (Why is no real title available?)
• scientific article; zbMATH DE number 3225111 (Why is no real title available?)
• Pancyclic graphs. I
• Pancyclicity and NP-completeness in planar graphs
• Quantum private communication

Cited in

(14)

• Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
• Subgraph complementation
• Complexity of vertex switching on edge-bicolored graphs
• On the hardness of switching to a small number of edges
• Switching to hedgehog-free graphs is NP-complete
• The embedding problem for switching classes of graphs
• SWITCHING GRAPHS
• scientific article; zbMATH DE number 17815 (Why is no real title available?)
• GETGRATS: a summary of scientific results (with annotated bibliography)
• Partial complementation of graphs
• An Algorithmic Study of Switch Graphs
• Complexity of hypergraph coloring and Seidel's switching.
• Switching classes: characterization and computation
• On the hardness of switching to a small number of edges

This page was built for publication: Complexity issues in switching of graphs

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