``Global'' graph problems tend to be intractable
type: Item
instance of: scholarly article
title: ``Global'' graph problems tend to be intractable
zbMATH Open document ID: 0615.68036
DOI: 10.1016/0022-0000(86)90038-3
author: N. Lakshmipathy
author: Karl Winklmann
published in: Journal of Computer and System Sciences
publication date: 1986-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 3997165
zbMATH Keywords: measure of globality
zbMATH Keywords: information-flow complexity
zbMATH Keywords: intractable problems
zbMATH Keywords: vertex cover
zbMATH Keywords: graph 3-colorability
zbMATH Keywords: Hamiltonian circuit
zbMATH Keywords: NP-complete problems
zbMATH Keywords: edge cover
zbMATH Keywords: graph 2-colorability
zbMATH Keywords: Eulerian circuit
zbMATH Keywords: problems in P
MaRDI profile type: Publication
full work available at URL: 0022-0000(86)90038-3
OpenAlex ID: W2012734500
cites work: Information transfer and area-time tradeoffs for VLSI multiplication
cites work: The Transitive Reduction of a Directed Graph
cites work: TWO THEOREMS IN GRAPH THEORY
cites work: Q3277097
cites work: Q5782525
cites work: Paths, Trees, and Flowers
cites work: Q3883524
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: A separator theorem for graphs of bounded genus
cites work: Parallel concepts in graph theory
cites work: Q4142699
cites work: Q4057549
cites work: Q4130999
cites work: A Separator Theorem for Planar Graphs
cites work: Applications of a Planar Separator Theorem
cites work: Q3725545
cites work: An Algorithm for a Minimum Cover of a Graph
cites work: Q4739657
cites work: Communication complexity
cites work: Q4144192
cites work: Q4010349
Recommended article: Problems concerning global connectivity of directed graphs
Recommended article: Hardness results of global total \(k\)-domination problem in graphs
Recommended article: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
Recommended article: Some new perspectives on global domination in graphs
Recommended article: Multistage graph problems on a global budget
Recommended article: Non-local probes do not help with many graph problems
Recommended article: Problems remaining NP-complette for sparse or dense graphs
Recommended article: Q4982914
Recommended article: Q3139286
description: scientific article; zbMATH DE number 3997165