Joseph Malkevitch
  • Member for 11 years, 4 months
  • Last seen more than 2 years ago
Conjectures implying Four Color Theorem
18 votes

Look at T. Saaty, Thirteen colorful variations on Guthrie's 4-color conjecture, American Math. Monthly, 79 (1972) 2-43 for many examples. Also, in David Barnette's book Map Coloring, Polyhedra, and ...

View answer
Social choice, arrow's theorem and open problems ?
12 votes

There are many complexity issues that are related to many of the topics that come up in what has come to be called social choice theory. These include the complexity of deciding who is the winner when ...

View answer
Projective Plane of Order 12
Accepted answer
9 votes

(More a comment than answer:) Finite projective planes exist for values of n which are powers of a prime, and there are infinitely many values of n which are ruled out by a theorem of R.H. Bruck and ...

View answer
Counting the number of Hamiltonian cycles in cubic Hamiltonian graphs?
8 votes

Some graphs have exactly three hamiltonian circuits: http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190060218/abstract If one starts with the plane graph of the tetrahedron, which contains exactly ...

View answer
Why does the Fibonacci sequence produce a worst-case Huffman encoding?
7 votes

This paper may shed some light on the issues: http://www.springerlink.com/content/w32x70520k8jj617/

View answer
About properties of adjacency matrix when a graph is planar
6 votes

While not directly related to your question you might want to look at the work on degree sequences of planar graphs. There are no known characterizations of when a degree sequence is the degree ...

View answer
What's the complexity of this estate-division game?
Accepted answer
6 votes

Perhaps this paper will be of interest though I don't know if it addresses complexity issues: http://or.journal.informs.org/cgi/content/abstract/19/2/270 or http://www.jstor.org/pss/169267

View answer
Edge-partitioning cubic graphs into claws and paths
6 votes

Perhaps this paper may be of interest: Kleinschmidt, Peter Regular partitions of regular graphs. Canad. Math. Bull. 21 (1978), no. 2, 177–181. It deals with graphs which can be written as the union ...

View answer
graphs from real-life problems
5 votes

Information related to test problems for the Traveling Salesman Problem (TSP) can be found here: http://www.tsp.gatech.edu/data/index.html

View answer
What is a really good problem to get your hands dirty in computational-geometry?
5 votes

Victor Klee in 1973 posed a problem about guarding simple polygons (sensors to protect an art gallery placed at its vertices) that has blossomed into hundreds of papers dealing with what has come to ...

View answer
Complexity of edge coloring in planar graphs
4 votes

You might find this paper of interest: http://cs.nyu.edu/cole/papers/edge_col.pdf

View answer
Using error-correcting codes in theory
4 votes

For a very nice account of how error-correcting codes are used in a particular practical situation look at: The Mathematics of the Compact Disc, by Jack H. Van Lint, in Mathematics Everywhere, M. ...

View answer
Algorithmic game theory - nonstandard equilibrium concepts?
4 votes

Joseph Y. Halpern from Cornell recently gave a talk at the CUNY Graduate Center with the title: Beyond Nash Equilibrium: Solution Concepts for the 21st Century. Perhaps his work would be of interest ...

View answer
Classes of graphs with easy Hamiltonian cycle but NP-hard TSP
3 votes

There are many infinite classes of graphs which are known to have hamiltonian circuits. Two especially interesting classes are the n-cubes and the Halin graphs. One way of thinking of the Halin graphs ...

View answer
Can we partition NP-complete problem into finite number of polynomially solvable problems?
3 votes

Take a look at: http://en.wikipedia.org/wiki/Parameterized_complexity

View answer
What is known about solutions to sparse integer linear programming problems?
3 votes

You may find this account of interest: http://en.wikipedia.org/wiki/Polyhedral_combinatorics and in particular the article by G. Ziegler: Lectures on 0-1 polytopes in: Kalai, Gil; Ziegler, ...

View answer
Decomposition of edges of eulerian graph into maximum number of cycles
2 votes

This paper may be helpful with regard to the question you raised: https://pdfs.semanticscholar.org/32a0/821e384e726819155065f7bc26e2d57329e5.pdf

View answer
Is any chordal graph an incomparability graph?
2 votes

A book source for information about problems of this type is: Graph Classes: A Survey, A. Brandstadt, Le, and Spinrad, SIAM, 1999.

View answer
Complexity of counting m-cycles in a graph with n nodes
2 votes

Perhaps this paper which deals with cycle lengths in planar graphs might be of value: Li, Ming-Chu; Corneil, Derek G.; Mendelsohn, Eric (2000), "Pancyclicity and NP-completeness in planar graphs", ...

View answer
Simple and practical deterministic algorithm, complicated running time
2 votes

This example, while not meeting the letter of your request may be of interest because it bears some spiritual affinity. Specifically, the question of sorting stacks of pancakes and burnt pancakes by ...

View answer
Upper bounds on the length of longest simple path in non-Hamiltonian graph?
2 votes

Questions of this kind are especially interesting for graphs which are 3-polytopal (edge-vertex graphs of 3-dimensional convex polytopes) and for the case of the graph being bipartite. (Also for ...

View answer
What are the main sub-areas of theoretical computer science?
2 votes

If you look at: http://arxiv.org/ you can see how they organize the different parts of Computer Science and also see the relative number of contributions that are being posted to the different parts....

View answer
polygonal triangulation and 3-colorability
2 votes

(This really is a comment on the prior answer.) If one has a maximal plane graph where all of the 3-circuits bound faces then the graph has a hamiltonian circuit by a theorem due to Hassler Whitney. ...

View answer
What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?
1 votes

Interesting results on this issue can be found on pages 24 and 25 of the book: The Stable Marriage Problem by Dan Gusfield and Robert Irving, MIT Press, 1989.

View answer
Is there any other algorithm whose worst-case running time is exponential meanwhile it works very well in practice other than Simplex Algorithm?
1 votes

Bin packing (many variants) is a problem whose complexity is known to be NP-hard: http://en.wikipedia.org/wiki/Bin_packing_problem However, many heuristics when applied to "practical" versions do ...

View answer
Polynomial time approximation algorithms for machine scheduling: how many open problems are left?
1 votes

This web page may have some information of use: http://www.mathematik.uni-osnabrueck.de/research/OR/class/

View answer
Counting complexity of a scheduling problem.
1 votes

A good reference for scheduling problems, including issues of complexity is: Handbook of Scheduling, J. Y-T. Leung (ed), Chapman & Hall/CRC, 2004.

View answer
Applications of Hamiltonian Cycle Problem
0 votes

The TSP often appears as part of more "complicated" operations research problems. A good example being the vehicle routing problem which has many variants. The following web site tracks some of the ...

View answer
Resources on Jablon's Protocol
0 votes

There are lots of papers on the general topic of password authentification on this web page: http://www.jablon.org/passwordlinks.html

View answer
Complexity of the Hamiltonian Subcycle problem
0 votes

You might find the methods that Joe Mitchell (CS-Stony Brook) has developed for treating a wide variety of geometrical problems that generalize the TSP to be of interest. Some of these papers can be ...

View answer