Paper by Erik D. Demaine

Reference:

Erik D. Demaine and MohammadTaghi Hajiaghayi, “Quickly Deciding Minor-Closed Parameters in General Graphs”, European Journal of Combinatorics, volume 28, number 1, January 2007, pages 311–314.

BibTeX

@Article{GeneralGraphs_EJC,
  AUTHOR        = {Erik D. Demaine and MohammadTaghi Hajiaghayi},
  TITLE         = {Quickly Deciding Minor-Closed Parameters in General Graphs},
  JOURNAL       = {European Journal of Combinatorics},
  journalurl    = {http://www.elsevier.com/wps/product/cws_home/622824},
  VOLUME        = 28,
  NUMBER        = 1,
  MONTH         = {January},
  YEAR          = 2007,
  PAGES         = {311--314},

  doi           = {https://dx.doi.org/10.1016/J.EJC.2005.07.003},
  dblp          = {https://dblp.org/rec/journals/ejc/DemaineH07},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1016/j.ejc.2005.07.003">ScienceDirect</A>.},
  length        = {4 pages},
  withstudent   = 1,
}

Abstract:

We construct algorithms for deciding essentially any minor-closed parameter, with explicit time bounds. This result strengthens previous results by Robertson and Seymour [1,2], Frick and Grohe [3], and Fellows and Langston [4] toward obtaining fixed-parameter algorithms for a general class of parameters.

Comments:

This paper is also available from ScienceDirect.

Length:

The paper is 4 pages.

Availability:

The paper is available in PostScript (115k), gzipped PostScript (46k), and PDF (72k).

See information on file formats.

[Google Scholar search]