On the Hardness of Switching to a Small Number of Edges

DOI10.1007/978-3-319-42634-1_13zbMath1477.68232arXiv1603.00254OpenAlexW2291381314MaRDI QIDQ2817858

Jan Kratochvíl, Vít Jelínek, Eva Jelínková

Publication date: 2 September 2016

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

Full work available at URL: https://arxiv.org/abs/1603.00254

zbMATH Keywords

computational complexityNP-completenessgraph densitySeidel's switchingswitching-minimal graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph operations (line graphs, products, etc.) (05C76) Density (toughness, etc.) (05C42)

Related Items (2)

Subgraph complementation ⋮ Partial complementation of graphs

Cites Work

• Unnamed Item
• On Gromov's method of selecting heavily covered points
• Some simplified NP-complete graph problems
• Speeding up Graph Algorithms via Switching Classes
• On graphs with maximum size in their switching classes
• On Switching to H‐Free Graphs
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: On the Hardness of Switching to a Small Number of Edges