``Global graph problems tend to be intractable

DOI10.1016/0022-0000(86)90038-3MaRDI QIDQ1820581zbMATH OpenOpenAlexFDO

Authors 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

edge coverEulerian circuitgraph 2-colorabilitygraph 3-colorabilityHamiltonian circuitinformation-flow complexityintractable problemsmeasure of globalityNP-complete problemsproblems in Pvertex cover

Mathematics Subject Classification ID

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

Recommendations

• Problems concerning global connectivity of directed graphs
• Hardness results of global total \(k\)-domination problem in graphs
• Hardness results of global total k-domination problem in graphs
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Some new perspectives on global domination in graphs
• Multistage graph problems on a global budget
• Non-local probes do not help with many graph problems
• Problems remaining NP-complette for sparse or dense graphs
• scientific article; zbMATH DE number 6424505
• scientific article; zbMATH DE number 434494

Cites work

• A separator theorem for graphs of bounded genus
• A Separator Theorem for Planar Graphs
• An Algorithm for a Minimum Cover of a Graph
• Applications of a Planar Separator Theorem
• Communication complexity
• scientific article; zbMATH DE number 3159208 (Why is no real title available?)
• scientific article; zbMATH DE number 3956440 (Why is no real title available?)
• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 65738 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3573250 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Information transfer and area-time tradeoffs for VLSI multiplication
• Parallel concepts in graph theory
• Paths, Trees, and Flowers
• Some simplified NP-complete graph problems
• The Transitive Reduction of a Directed Graph
• TWO THEOREMS IN GRAPH THEORY

Cited in

(4)

• The Mapmaker's dilemma
• On limitations of transformations between combinatorial problems
• The communication complexity of enumeration, elimination, and selection
• Multistage graph problems on a global budget

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

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