``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 coververtex coverNP-complete problemsHamiltonian circuitintractable 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)

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

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

Cited in

(4)

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

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)