Catalònica: Aggregator of digital content of Catalunya > Log data

It's in  › Log data

Linked Open Data

1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor

Resource identifiers

Demaine, E., Hajiaghayi, M., Thilikos, D. "1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor". 2002.

http://hdl.handle.net/2117/97497

Origin

(Universitat Politècnica de Catalunya. UPCommons - Recerca)

File

Title:: 1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor
Subject:: Àrees temàtiques de la UPC::Informàtica; Treewidth of graphs; Polynomial-time constant-factor approximation algorithms
Description:: We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The approximation factors are 1.5 for treewidth and 2.25 for branchwidth. In particular, our result directly applies to classes of nonplanar graphs such as K_{5}-minor-free graphs and K_{3,3}-minor-free graphs. Along the way, we present a polynomial-time algorithm to decompose H-minor-free graphs into planar graphs and graphs of treewidth at most c_H (a constant dependent on H) using clique sums. This result has several applications in designing fully polynomial-time approximation schemes and fixed-parameter algorithms for many NP-complete problems on these graphs.; Postprint (published version)
Idioma:: English
Relationship:: LSI-02-40-R
Author/Producer:: Demaine, Erik D.; Hajiaghayi, Mohammad Taghi; Thilikos Touloupas, Dimitrios
Other collaborators/producers:: Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
Rights:: Open Access
Date:: 2002-05
Resource type:: External research report
Format:: 11 p.; application/postscript

oai_dc

<?xml version="1.0" encoding="UTF-8" ?>

< oai_dc:dc schemaLocation =" http://www.openarchives.org/OAI/2.0/oai_dc/ http://www.openarchives.org/OAI/2.0/oai_dc.xsd " >
1. < dc:title > 1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor </ dc:title >
2. < dc:creator > Demaine, Erik D. </ dc:creator >
3. < dc:creator > Hajiaghayi, Mohammad Taghi </ dc:creator >
4. < dc:creator > Thilikos Touloupas, Dimitrios </ dc:creator >
5. < dc:contributor > Universitat Politècnica de Catalunya. Departament de Ciències de la Computació </ dc:contributor >
6. < dc:subject > Àrees temàtiques de la UPC::Informàtica </ dc:subject >
7. < dc:subject > Treewidth of graphs </ dc:subject >
8. < dc:subject > Polynomial-time constant-factor approximation algorithms </ dc:subject >
9. < dc:description > We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The approximation factors are 1.5 for treewidth and 2.25 for branchwidth. In particular, our result directly applies to classes of nonplanar graphs such as K_{5}-minor-free graphs and K_{3,3}-minor-free graphs. Along the way, we present a polynomial-time algorithm to decompose H-minor-free graphs into planar graphs and graphs of treewidth at most c_H (a constant dependent on H) using clique sums. This result has several applications in designing fully polynomial-time approximation schemes and fixed-parameter algorithms for many NP-complete problems on these graphs. </ dc:description >
10. < dc:description > Postprint (published version) </ dc:description >
11. < dc:date > 2002-05 </ dc:date >
12. < dc:type > External research report </ dc:type >
13. < dc:identifier > Demaine, E., Hajiaghayi, M., Thilikos, D. "1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor". 2002. </ dc:identifier >
14. < dc:identifier > http://hdl.handle.net/2117/97497 </ dc:identifier >
15. < dc:language > eng </ dc:language >
16. < dc:relation > LSI-02-40-R </ dc:relation >
17. < dc:rights > Open Access </ dc:rights >
18. < dc:format > 11 p. </ dc:format >
19. < dc:format > application/postscript </ dc:format >
</ oai_dc:dc >

didl

<?xml version="1.0" encoding="UTF-8" ?>

< d:DIDL schemaLocation =" urn:mpeg:mpeg21:2002:02-DIDL-NS http://standards.iso.org/ittf/PubliclyAvailableStandards/MPEG-21_schema_files/did/didl.xsd " >
1. < d:DIDLInfo >
  1. < dcterms:created schemaLocation =" http://purl.org/dc/terms/ http://dublincore.org/schemas/xmls/qdc/dcterms.xsd " > 2016-11-30T11:38:22Z </ dcterms:created >
  </ d:DIDLInfo >
2. < d:Item id =" hdl_2117_97497 " >
  1. < d:Descriptor >
    1. < d:Statement mimeType =" application/xml; charset=utf-8 " >
      1. < dii:Identifier schemaLocation =" urn:mpeg:mpeg21:2002:01-DII-NS http://standards.iso.org/ittf/PubliclyAvailableStandards/MPEG-21_schema_files/dii/dii.xsd " > urn:hdl:2117/97497 </ dii:Identifier >
      </ d:Statement >
    </ d:Descriptor >
  2. < d:Descriptor >
    1. < d:Statement mimeType =" application/xml; charset=utf-8 " >
      1. < oai_dc:dc schemaLocation =" http://www.openarchives.org/OAI/2.0/oai_dc/ http://www.openarchives.org/OAI/2.0/oai_dc.xsd " >
        
        < dc:title > 1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor </ dc:title >
        
        < dc:creator > Demaine, Erik D. </ dc:creator >
        
        < dc:creator > Hajiaghayi, Mohammad Taghi </ dc:creator >
        
        < dc:creator > Thilikos Touloupas, Dimitrios </ dc:creator >
        
        < dc:contributor > Universitat Politècnica de Catalunya. Departament de Ciències de la Computació </ dc:contributor >
        
        < dc:subject > Àrees temàtiques de la UPC::Informàtica </ dc:subject >
        
        < dc:description > We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The approximation factors are 1.5 for treewidth and 2.25 for branchwidth. In particular, our result directly applies to classes of nonplanar graphs such as K_{5}-minor-free graphs and K_{3,3}-minor-free graphs. Along the way, we present a polynomial-time algorithm to decompose H-minor-free graphs into planar graphs and graphs of treewidth at most c_H (a constant dependent on H) using clique sums. This result has several applications in designing fully polynomial-time approximation schemes and fixed-parameter algorithms for many NP-complete problems on these graphs. </ dc:description >
        
        < dc:date > 2016-11-30T11:38:22Z </ dc:date >
        
        < dc:date > 2016-11-30T11:38:22Z </ dc:date >
        
        < dc:date > 2002-05 </ dc:date >
        
        < dc:type > External research report </ dc:type >
        
        < dc:identifier > Demaine, E., Hajiaghayi, M., Thilikos, D. "1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor". 2002. </ dc:identifier >
        
        < dc:identifier > http://hdl.handle.net/2117/97497 </ dc:identifier >
        
        < dc:language > eng </ dc:language >
        
        < dc:relation > LSI-02-40-R </ dc:relation >
        
        < dc:rights > Open Access </ dc:rights >
        
        </ oai_dc:dc >
      </ d:Statement >
    </ d:Descriptor >
  3. < d:Component id =" 2117_97497_1 " >
    1. < d:Resource mimeType =" application/postscript " ref =" https://upcommons.upc.edu/bitstream/2117/97497/1/R02-40.ps " />
    </ d:Component >
  </ d:Item >
</ d:DIDL >

edm

<?xml version="1.0" encoding="UTF-8" ?>

< rdf:RDF schemaLocation =" http://www.w3.org/1999/02/22-rdf-syntax-ns# http://www.europeana.eu/schemas/edm/EDM.xsd " >
1. < edm:ProvidedCHO about =" https://catalonica.bnc.cat/catalonicahub/lod/oai:upcommons.upc.edu:2117_--_97497#ent0 " >
  1. < dc:contributor > Universitat Politècnica de Catalunya. Departament de Ciències de la Computació </ dc:contributor >
  2. < dc:creator > Demaine, Erik D. </ dc:creator >
  3. < dc:creator > Hajiaghayi, Mohammad Taghi </ dc:creator >
  4. < dc:creator > Thilikos Touloupas, Dimitrios </ dc:creator >
  5. < dc:date > 2002-05 </ dc:date >
  6. < dc:description > We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The approximation factors are 1.5 for treewidth and 2.25 for branchwidth. In particular, our result directly applies to classes of nonplanar graphs such as K_{5}-minor-free graphs and K_{3,3}-minor-free graphs. Along the way, we present a polynomial-time algorithm to decompose H-minor-free graphs into planar graphs and graphs of treewidth at most c_H (a constant dependent on H) using clique sums. This result has several applications in designing fully polynomial-time approximation schemes and fixed-parameter algorithms for many NP-complete problems on these graphs. </ dc:description >
  7. < dc:description > Postprint (published version) </ dc:description >
  8. < dc:identifier > Demaine, E., Hajiaghayi, M., Thilikos, D. "1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor". 2002. </ dc:identifier >
  9. < dc:identifier > http://hdl.handle.net/2117/97497 </ dc:identifier >
  10. < dc:language > eng </ dc:language >
  11. < dc:relation > LSI-02-40-R </ dc:relation >
  12. < dc:rights > Open Access </ dc:rights >
  13. < dc:subject > Àrees temàtiques de la UPC::Informàtica </ dc:subject >
  14. < dc:subject > Treewidth of graphs </ dc:subject >
  15. < dc:subject > Polynomial-time constant-factor approximation algorithms </ dc:subject >
  16. < dc:title > 1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor </ dc:title >
  17. < dc:type > External research report </ dc:type >
  18. < edm:type > TEXT </ edm:type >
  </ edm:ProvidedCHO >
2. < ore:Aggregation about =" https://catalonica.bnc.cat/catalonicahub/lod/oai:upcommons.upc.edu:2117_--_97497#ent1 " >
  1. < edm:aggregatedCHO resource =" https://catalonica.bnc.cat/catalonicahub/lod/oai:upcommons.upc.edu:2117_--_97497#ent0 " />
  2. < edm:dataProvider > Universitat Politècnica de Catalunya. UPCommons - Recerca </ edm:dataProvider >
  3. < edm:isShownAt resource =" http://hdl.handle.net/2117/97497 " />
  4. < edm:isShownBy resource =" https://upcommons.upc.edu/bitstream/2117/97497/1/R02-40.ps " />
  5. < edm:provider > Catalònica </ edm:provider >
  6. < edm:rights resource =" http://creativecommons.org/licenses/by-nc-nd/4.0/ " />
  </ ore:Aggregation >
</ rdf:RDF >

marc

<?xml version="1.0" encoding="UTF-8" ?>

< record schemaLocation =" http://www.loc.gov/MARC21/slim http://www.loc.gov/standards/marcxml/schema/MARC21slim.xsd " >
1. < leader > 00925njm 22002777a 4500 </ leader >
2. < datafield ind1 =" " ind2 =" " tag =" 042 " >
  1. < subfield code =" a " > dc </ subfield >
  </ datafield >
3. < datafield ind1 =" " ind2 =" " tag =" 720 " >
  1. < subfield code =" a " > Demaine, Erik D. </ subfield >
  2. < subfield code =" e " > author </ subfield >
  </ datafield >
4. < datafield ind1 =" " ind2 =" " tag =" 720 " >
  1. < subfield code =" a " > Hajiaghayi, Mohammad Taghi </ subfield >
  2. < subfield code =" e " > author </ subfield >
  </ datafield >
5. < datafield ind1 =" " ind2 =" " tag =" 720 " >
  1. < subfield code =" a " > Thilikos Touloupas, Dimitrios </ subfield >
  2. < subfield code =" e " > author </ subfield >
  </ datafield >
6. < datafield ind1 =" " ind2 =" " tag =" 260 " >
  1. < subfield code =" c " > 2002-05 </ subfield >
  </ datafield >
7. < datafield ind1 =" " ind2 =" " tag =" 520 " >
  1. < subfield code =" a " > We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The approximation factors are 1.5 for treewidth and 2.25 for branchwidth. In particular, our result directly applies to classes of nonplanar graphs such as K_{5}-minor-free graphs and K_{3,3}-minor-free graphs. Along the way, we present a polynomial-time algorithm to decompose H-minor-free graphs into planar graphs and graphs of treewidth at most c_H (a constant dependent on H) using clique sums. This result has several applications in designing fully polynomial-time approximation schemes and fixed-parameter algorithms for many NP-complete problems on these graphs. </ subfield >
  </ datafield >
8. < datafield ind1 =" 8 " ind2 =" " tag =" 024 " >
  1. < subfield code =" a " > Demaine, E., Hajiaghayi, M., Thilikos, D. "1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor". 2002. </ subfield >
  </ datafield >
9. < datafield ind1 =" 8 " ind2 =" " tag =" 024 " >
  1. < subfield code =" a " > http://hdl.handle.net/2117/97497 </ subfield >
  </ datafield >
10. < datafield ind1 =" " ind2 =" " tag =" 653 " >
  1. < subfield code =" a " > Àrees temàtiques de la UPC::Informàtica </ subfield >
  </ datafield >
11. < datafield ind1 =" 0 " ind2 =" 0 " tag =" 245 " >
  1. < subfield code =" a " > 1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor </ subfield >
  </ datafield >
</ record >

mets

<?xml version="1.0" encoding="UTF-8" ?>

< mets ID =" DSpace_ITEM_2117-97497 " OBJID =" hdl:2117/97497 " PROFILE =" DSpace METS SIP Profile 1.0 " TYPE =" DSpace ITEM " schemaLocation =" http://www.loc.gov/METS/ http://www.loc.gov/standards/mets/mets.xsd " >
1. < metsHdr CREATEDATE =" 2024-09-05T04:46:12Z " >
  1. < agent ROLE =" CUSTODIAN " TYPE =" ORGANIZATION " >
    1. < name > UPCommons. Portal del coneixement obert de la UPC </ name >
    </ agent >
  </ metsHdr >
2. < dmdSec ID =" DMD_2117_97497 " >
  1. < mdWrap MDTYPE =" MODS " >
    1. < xmlData schemaLocation =" http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-1.xsd " >
      1. < mods:mods schemaLocation =" http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-1.xsd " >
        
        < mods:name >
        
        < mods:role >
        
        < mods:roleTerm type =" text " > author </ mods:roleTerm >
        
        </ mods:role >
        
        < mods:namePart > Demaine, Erik D. </ mods:namePart >
        
        </ mods:name >
        
        < mods:name >
        
        < mods:role >
        
        < mods:roleTerm type =" text " > author </ mods:roleTerm >
        
        </ mods:role >
        
        < mods:namePart > Hajiaghayi, Mohammad Taghi </ mods:namePart >
        
        </ mods:name >
        
        < mods:name >
        
        < mods:role >
        
        < mods:roleTerm type =" text " > author </ mods:roleTerm >
        
        </ mods:role >
        
        < mods:namePart > Thilikos Touloupas, Dimitrios </ mods:namePart >
        
        </ mods:name >
        
        < mods:name >
        
        < mods:role >
        
        < mods:roleTerm type =" text " > other </ mods:roleTerm >
        
        </ mods:role >
        
        < mods:namePart > Universitat Politècnica de Catalunya. Departament de Ciències de la Computació </ mods:namePart >
        
        </ mods:name >
        
        < mods:extension >
        
        < mods:dateAccessioned encoding =" iso8601 " > 2016-11-30T11:38:22Z </ mods:dateAccessioned >
        
        </ mods:extension >
        
        < mods:extension >
        
        < mods:dateAvailable encoding =" iso8601 " > 2016-11-30T11:38:22Z </ mods:dateAvailable >
        
        </ mods:extension >
        
        < mods:originInfo >
        
        < mods:dateIssued encoding =" iso8601 " > 2002-05 </ mods:dateIssued >
        
        </ mods:originInfo >
        
        < mods:identifier type =" citation " > Demaine, E., Hajiaghayi, M., Thilikos, D. "1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor". 2002. </ mods:identifier >
        
        < mods:identifier type =" uri " > http://hdl.handle.net/2117/97497 </ mods:identifier >
        
        < mods:abstract > We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The approximation factors are 1.5 for treewidth and 2.25 for branchwidth. In particular, our result directly applies to classes of nonplanar graphs such as K_{5}-minor-free graphs and K_{3,3}-minor-free graphs. Along the way, we present a polynomial-time algorithm to decompose H-minor-free graphs into planar graphs and graphs of treewidth at most c_H (a constant dependent on H) using clique sums. This result has several applications in designing fully polynomial-time approximation schemes and fixed-parameter algorithms for many NP-complete problems on these graphs. </ mods:abstract >
        
        < mods:language >
        
        < mods:languageTerm authority =" rfc3066 " > eng </ mods:languageTerm >
        
        </ mods:language >
        
        < mods:accessCondition type =" useAndReproduction " />
        
        < mods:subject >
        
        < mods:topic > Àrees temàtiques de la UPC::Informàtica </ mods:topic >
        
        </ mods:subject >
        
        < mods:titleInfo >
        
        < mods:title > 1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor </ mods:title >
        
        </ mods:titleInfo >
        
        < mods:genre > External research report </ mods:genre >
        
        </ mods:mods >
      </ xmlData >
    </ mdWrap >
  </ dmdSec >
3. < amdSec ID =" FO_2117_97497_1 " >
  1. < techMD ID =" TECH_O_2117_97497_1 " >
    1. < mdWrap MDTYPE =" PREMIS " >
      1. < xmlData schemaLocation =" http://www.loc.gov/standards/premis http://www.loc.gov/standards/premis/PREMIS-v1-0.xsd " >
        
        < premis:premis >
        
        < premis:object >
        
        < premis:objectIdentifier >
        
        < premis:objectIdentifierType > URL </ premis:objectIdentifierType >
        
        < premis:objectIdentifierValue > https://upcommons.upc.edu/bitstream/2117/97497/1/R02-40.ps </ premis:objectIdentifierValue >
        
        </ premis:objectIdentifier >
        
        < premis:objectCategory > File </ premis:objectCategory >
        
        < premis:objectCharacteristics >
        
        < premis:fixity >
        
        < premis:messageDigestAlgorithm > MD5 </ premis:messageDigestAlgorithm >
        
        < premis:messageDigest > 319242120e41765c16669265c113d3b5 </ premis:messageDigest >
        
        </ premis:fixity >
        
        < premis:size > 188524 </ premis:size >
        
        < premis:format >
        
        < premis:formatDesignation >
        
        < premis:formatName > application/postscript </ premis:formatName >
        
        </ premis:formatDesignation >
        
        </ premis:format >
        
        </ premis:objectCharacteristics >
        
        < premis:originalName > R02-40.ps </ premis:originalName >
        
        </ premis:object >
        
        </ premis:premis >
        
        </ xmlData >
      </ mdWrap >
    </ techMD >
  </ amdSec >
4. < fileSec >
  1. < fileGrp USE =" ORIGINAL " >
    1. < file ADMID =" FO_2117_97497_1 " CHECKSUM =" 319242120e41765c16669265c113d3b5 " CHECKSUMTYPE =" MD5 " GROUPID =" GROUP_BITSTREAM_2117_97497_1 " ID =" BITSTREAM_ORIGINAL_2117_97497_1 " MIMETYPE =" application/postscript " SEQ =" 1 " SIZE =" 188524 " >
      1. < FLocat LOCTYPE =" URL " href =" https://upcommons.upc.edu/bitstream/2117/97497/1/R02-40.ps " type =" simple " />
      </ file >
    </ fileGrp >
  </ fileSec >
5. < structMap LABEL =" DSpace Object " TYPE =" LOGICAL " >
  1. < div ADMID =" DMD_2117_97497 " TYPE =" DSpace Object Contents " >
    1. < div TYPE =" DSpace BITSTREAM " >
      1. < fptr FILEID =" BITSTREAM_ORIGINAL_2117_97497_1 " />
      </ div >
    </ div >
  </ structMap >
</ mets >

mods

<?xml version="1.0" encoding="UTF-8" ?>

< mods:mods schemaLocation =" http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-1.xsd " >
1. < mods:name >
  1. < mods:namePart > Demaine, Erik D. </ mods:namePart >
  </ mods:name >
2. < mods:name >
  1. < mods:namePart > Hajiaghayi, Mohammad Taghi </ mods:namePart >
  </ mods:name >
3. < mods:name >
  1. < mods:namePart > Thilikos Touloupas, Dimitrios </ mods:namePart >
  </ mods:name >
4. < mods:extension >
  1. < mods:dateAvailable encoding =" iso8601 " > 2016-11-30T11:38:22Z </ mods:dateAvailable >
  </ mods:extension >
5. < mods:extension >
  1. < mods:dateAccessioned encoding =" iso8601 " > 2016-11-30T11:38:22Z </ mods:dateAccessioned >
  </ mods:extension >
6. < mods:originInfo >
  1. < mods:dateIssued encoding =" iso8601 " > 2002-05 </ mods:dateIssued >
  </ mods:originInfo >
7. < mods:identifier type =" citation " > Demaine, E., Hajiaghayi, M., Thilikos, D. "1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor". 2002. </ mods:identifier >
8. < mods:identifier type =" uri " > http://hdl.handle.net/2117/97497 </ mods:identifier >
9. < mods:abstract > We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The approximation factors are 1.5 for treewidth and 2.25 for branchwidth. In particular, our result directly applies to classes of nonplanar graphs such as K_{5}-minor-free graphs and K_{3,3}-minor-free graphs. Along the way, we present a polynomial-time algorithm to decompose H-minor-free graphs into planar graphs and graphs of treewidth at most c_H (a constant dependent on H) using clique sums. This result has several applications in designing fully polynomial-time approximation schemes and fixed-parameter algorithms for many NP-complete problems on these graphs. </ mods:abstract >
10. < mods:language >
  1. < mods:languageTerm > eng </ mods:languageTerm >
  </ mods:language >
11. < mods:accessCondition type =" useAndReproduction " > Open Access </ mods:accessCondition >
12. < mods:subject >
  1. < mods:topic > Àrees temàtiques de la UPC::Informàtica </ mods:topic >
  </ mods:subject >
13. < mods:titleInfo >
  1. < mods:title > 1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor </ mods:title >
  </ mods:titleInfo >
14. < mods:genre > External research report </ mods:genre >
</ mods:mods >

qdc

<?xml version="1.0" encoding="UTF-8" ?>

< qdc:qualifieddc schemaLocation =" http://purl.org/dc/elements/1.1/ http://dublincore.org/schemas/xmls/qdc/2006/01/06/dc.xsd http://purl.org/dc/terms/ http://dublincore.org/schemas/xmls/qdc/2006/01/06/dcterms.xsd http://dspace.org/qualifieddc/ http://www.ukoln.ac.uk/metadata/dcmi/xmlschema/qualifieddc.xsd " >
1. < dc:title > 1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor </ dc:title >
2. < dc:creator > Demaine, Erik D. </ dc:creator >
3. < dc:creator > Hajiaghayi, Mohammad Taghi </ dc:creator >
4. < dc:creator > Thilikos Touloupas, Dimitrios </ dc:creator >
5. < dc:contributor > Universitat Politècnica de Catalunya. Departament de Ciències de la Computació </ dc:contributor >
6. < dc:subject > Àrea temàtica UPC: Informàtica </ dc:subject >
7. < dc:subject > Treewidth of graphs </ dc:subject >
8. < dc:subject > Polynomial-time constant-factor approximation algorithms </ dc:subject >
9. < dcterms:abstract > We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The approximation factors are 1.5 for treewidth and 2.25 for branchwidth. In particular, our result directly applies to classes of nonplanar graphs such as K_{5}-minor-free graphs and K_{3,3}-minor-free graphs. Along the way, we present a polynomial-time algorithm to decompose H-minor-free graphs into planar graphs and graphs of treewidth at most c_H (a constant dependent on H) using clique sums. This result has several applications in designing fully polynomial-time approximation schemes and fixed-parameter algorithms for many NP-complete problems on these graphs. </ dcterms:abstract >
10. < dcterms:dateAccepted > 2016-11-30T11:38:22Z </ dcterms:dateAccepted >
11. < dcterms:available > 2016-11-30T11:38:22Z </ dcterms:available >
12. < dcterms:issued > 2002-05 </ dcterms:issued >
13. < dc:type > External research report </ dc:type >
14. < dc:identifier type =" dcterms:URI " > http://hdl.handle.net/2117/97497 </ dc:identifier >
15. < dcterms:bibliographicCitation > Demaine, E., Hajiaghayi, M., Thilikos, D. "1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor". 2002. </ dcterms:bibliographicCitation >
16. < dc:language > eng </ dc:language >
17. < dc:relation > LSI-02-40-R </ dc:relation >
18. < dcterms:accessRights > Open Access </ dcterms:accessRights >
19. < dcterms:extent > 11 p. </ dcterms:extent >
20. < dcterms:identifier > https://upcommons.upc.edu/bitstream/2117/97497/2/R02-40.ps.jpg </ dcterms:identifier >
</ qdc:qualifieddc >

rdf

<?xml version="1.0" encoding="UTF-8" ?>

< rdf:RDF schemaLocation =" http://www.openarchives.org/OAI/2.0/rdf/ http://www.openarchives.org/OAI/2.0/rdf.xsd " >
1. < ow:Publication about =" oai:upcommons.upc.edu:2117/97497 " >
  1. < dc:title > 1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor </ dc:title >
  2. < dc:creator > Demaine, Erik D. </ dc:creator >
  3. < dc:creator > Hajiaghayi, Mohammad Taghi </ dc:creator >
  4. < dc:creator > Thilikos Touloupas, Dimitrios </ dc:creator >
  5. < dc:contributor > Universitat Politècnica de Catalunya. Departament de Ciències de la Computació </ dc:contributor >
  6. < dc:subject > Àrees temàtiques de la UPC::Informàtica </ dc:subject >
  7. < dc:description > We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The approximation factors are 1.5 for treewidth and 2.25 for branchwidth. In particular, our result directly applies to classes of nonplanar graphs such as K_{5}-minor-free graphs and K_{3,3}-minor-free graphs. Along the way, we present a polynomial-time algorithm to decompose H-minor-free graphs into planar graphs and graphs of treewidth at most c_H (a constant dependent on H) using clique sums. This result has several applications in designing fully polynomial-time approximation schemes and fixed-parameter algorithms for many NP-complete problems on these graphs. </ dc:description >
  8. < dc:date > 2016-11-30T11:38:22Z </ dc:date >
  9. < dc:date > 2016-11-30T11:38:22Z </ dc:date >
  10. < dc:date > 2002-05 </ dc:date >
  11. < dc:type > External research report </ dc:type >
  12. < dc:identifier > Demaine, E., Hajiaghayi, M., Thilikos, D. "1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor". 2002. </ dc:identifier >
  13. < dc:identifier > http://hdl.handle.net/2117/97497 </ dc:identifier >
  14. < dc:language > eng </ dc:language >
  15. < dc:relation > LSI-02-40-R </ dc:relation >
  16. < dc:rights > Open Access </ dc:rights >
  </ ow:Publication >
</ rdf:RDF >

Biblioteca de Catalunya Carrer de l'Hospital, 56. 08001 Barcelona Email: catalonica@bnc.cat Tlf.: +34 932 702 300

OAI Repository