On existence theorems

DOI10.1016/0012-365X(93)90180-2zbMATH Open0803.05046MaRDI QIDQ686508FDOQ686508

Authors: Svatopluk Poljak 

Publication date: 20 December 1993

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

existence theoremspolynomial time algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Games involving graphs (91A43)

Cites Work

• Title not available (Why is that?)
• On Hamilton's ideals
• Geometric algorithms and combinatorial optimization
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some Extremal Properties of Bipartite Subgraphs
• How easy is local search?
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• An algorithmic approach to the Lovász local lemma. I
• A Theorem on Planar Graphs
• A method in graph theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
• Splitting necklaces
• Complexity of Partial Satisfaction
• The Even Cycle Problem for Directed Graphs
• Title not available (Why is that?)
• Every 4-regular graph plus an edge contains a 3-regular subgraph
• Title not available (Why is that?)
• Bipartite Subgraphs of Triangle-Free Graphs
• Tournament Ranking with Expected Profit in Polynomial Time
• Title not available (Why is that?)
• A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Every 7-regular digraph contains an even cycle
• Title not available (Why is that?)
• Title not available (Why is that?)
• Illumination of convex discs
• Title not available (Why is that?)
• The Borsuk-Ulam Theorem and Bisection of Necklaces
• Title not available (Why is that?)
• Three-regular parts of four-regular graphs
• Balancing matrices with line shifts

Cited In (4)

• An existence theorem for elementar-contents
• Existence Proofs
• Regular codes in regular graphs are difficult
• The complexity of finding a second Hamiltonian cycle in cubic graphs

This page was built for publication: On existence theorems

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