``Global graph problems tend to be intractable

DOI10.1016/0022-0000(86)90038-3zbMath0615.68036OpenAlexW2012734500MaRDI QIDQ1820581

N. Lakshmipathy, Karl Winklmann

Publication date: 1986

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(86)90038-3

zbMATH Keywords

NP-complete problemsHamiltonian circuitedge coververtex coverintractable problemsEulerian circuitgraph 2-colorabilitygraph 3-colorabilityinformation-flow complexitymeasure of globalityproblems in P

Mathematics Subject Classification ID

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

Related Items (4)

On limitations of transformations between combinatorial problems ⋮ The Mapmaker's dilemma ⋮ The communication complexity of enumeration, elimination, and selection ⋮ Myhill-Nerode Methods for Hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Communication complexity
• Some simplified NP-complete graph problems
• Parallel concepts in graph theory
• A separator theorem for graphs of bounded genus
• TWO THEOREMS IN GRAPH THEORY
• An Algorithm for a Minimum Cover of a Graph
• Information transfer and area-time tradeoffs for VLSI multiplication
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• Paths, Trees, and Flowers
• The Transitive Reduction of a Directed Graph

This page was built for publication: ``Global graph problems tend to be intractable