About: Pathwidth

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Term in graph theory

Property	Value
dbo:description	Begriff aus der Graphentheorie (de) gráfelméleti fogalom (hu) term in graph theory (en) термін у теорії графів (uk)
dbo:thumbnail	wiki-commons:Special:FilePath/Pathwidth.jpg?width=300
dbo:wikiPageExternalLink	http://lca.ceid.upatras.gr/~kirousis/publications/j31.pdf http://www.springerlink.com/content/lamc6dynulxv7a8n/ http://www.emis.de/journals/DMTCS/volumes/abstracts/pdfpapers/dm030404.pdf http://igitur-archive.library.uu.nl/dissertations/01847381/full.pdf http://www.ii.uib.no/~telle/bib/BGT.pdf https://hal.inria.fr/inria-00070220/file/RR-5804.pdf https://hal.inria.fr/inria-00587819/file/paper-noformat.pdf http://cgm.cs.mcgill.ca/~msuder/schools/mcgill/research/trees/SOCS-02-8.pdf http://cg.scs.carleton.ca/~vida/pubs/papers/DMW-GD02.pdf https://web.archive.org/web/20030503103911/http:/cgm.cs.mcgill.ca/~msuder/schools/mcgill/research/trees/SOCS-02-8.pdf https://web.archive.org/web/20110721084127/http:/lca.ceid.upatras.gr/~kirousis/publications/j31.pdf https://web.archive.org/web/20110724173550/http:/igitur-archive.library.uu.nl/dissertations/01847381/full.pdf http://www.musanim.com/miller1956/
dbo:wikiPageWikiLink	dbr:Graph_drawing dbr:Space_complexity dbr:Planar_separator_theorem dbr:Circle_graph dbr:Tree_(graph_theory) dbr:Glossary_of_graph_theory dbr:Tree_decomposition dbr:Register_allocation dbr:Maximal_clique dbr:Maximum_clique dbc:Graph_invariants dbc:Graph_minor_theory dbr:Compiler dbr:Dual_graph dbr:Natural_language_processing dbr:Acta_Informatica dbr:Control_flow dbr:Lecture_Notes_in_Computer_Science dbr:Forbidden_graph_characterization dbr:Line_graph_of_a_hypergraph dbr:Crossing_number_(graph_theory) dbr:Complement_graph dbr:Strahler_number dbr:Split_graph dbr:High-level_programming_language dbr:Information_and_Computation dbr:Chordal_graph dbr:Interval_graph dbr:Directed_acyclic_graph dbr:Vertex_(graph_theory) dbr:Halin_graph dbr:Caterpillar_tree dbr:Graph_bandwidth dbr:Graph_embedding dbr:Graph_structure_theorem dbr:Graph_theory dbr:Bipartite_graph dbr:Subset dbr:Graph_coloring dbr:Hypergraph dbr:Algorithmica dbr:Clique-sum dbr:Cograph dbr:Theoretical_Computer_Science_(journal) dbr:Induced_subgraph dbr:Information_Processing_Letters dbr:Robertson–Seymour_theorem dbr:Linear_order dbr:Complete_graph dbr:Complete_bipartite_graph dbr:Graph_minor dbr:Cubic_graph dbr:Programmable_logic_array dbr:Maximal_element dbr:Outerplanar_graph dbr:International_Journal_of_Computational_Geometry_and_Applications dbr:Interval_order dbr:Psychological_Review dbr:Pursuit–evasion dbr:Tree-depth dbr:Utrecht_University dbr:Intersection_graph dbr:Journal_of_Combinatorial_Theory dbr:Boxicity dbr:Discrete_Mathematics_(journal) dbr:Distance-hereditary_graph dbr:Genus_(mathematics) dbr:Boolean_logic dbr:CMOS dbr:Computational_linguistics dbr:Line_graph dbr:Path_graph dbr:Treewidth dbr:Wagner's_theorem dbr:Degree_(graph_theory) dbr:Dynamic_programming dbr:Degeneracy_(graph_theory) dbr:Graph_(discrete_mathematics) dbr:Planar_graph dbr:Maximum_cut dbr:Clique-width dbr:Circular-arc_graph dbr:Comparability_graph dbr:Permutation_graph dbr:Perfect_graph dbr:Discrete_Applied_Mathematics dbr:VLSI dbr:Order_(journal) dbr:Journal_of_Graph_Theory dbr:Graphs_and_Combinatorics dbr:SIAM_Journal_on_Computing dbr:SIAM_Journal_on_Discrete_Mathematics dbr:Series–parallel_graph dbr:Cutwidth dbr:Combinatorics,_Probability_and_Computing dbr:NP-complete dbr:NP-hard dbr:Exponential_time dbr:Lower_bound dbr:Fixed-parameter_tractable dbr:File:Caterpillar_tree.svg dbr:Approximation_ratio dbr:Perfect_binary_tree dbr:Minimum_dominating_set dbr:Topological_ordering dbr:File:Interval_graph.svg dbr:File:Pathwidth-1_obstructions.svg dbr:File:Pathwidth.JPG
dbp:author1Link	Neil Robertson (en)
dbp:author2Link	Paul Seymour (en)
dbp:first	Paul (en) Neil (en)
dbp:last	Robertson (en) Seymour (en)
dbp:wikiPageUsesTemplate	dbt:Reflist dbt:Math dbt:Cite_journal dbt:Sub dbt:Sqrt dbt:Sup dbt:Citation dbt:Refend dbt:Sfnp dbt:Refbegin dbt:ProQuest dbt:CS1_config dbt:Mvar dbt:Abs dbt:Frac dbt:Harvp dbt:Harvs dbt:Harvtxt dbt:Unsolved dbt:Short_description
dbp:year	1983 (xsd:integer)
dct:subject	dbc:NP-complete_problems dbc:Graph_invariants dbc:Graph_minor_theory
gold:hypernym	dbr:Number
rdfs:label	Pathwidth (en) Pfadweite (de) Largura de Caminho (pt) Путевая ширина (ru) Шляхова ширина графа (uk)
owl:sameAs	freebase:Pathwidth yago-res:Pathwidth wikidata:Pathwidth dbpedia-de:Pathwidth dbpedia-pt:Pathwidth dbpedia-fa:Pathwidth dbpedia-ru:Pathwidth dbpedia-uk:Pathwidth dbpedia-global:Pathwidth
prov:wasDerivedFrom	wikipedia-en:Pathwidth?oldid=1278937763&ns=0
foaf:depiction	wiki-commons:Special:FilePath/Caterpillar_tree.svg wiki-commons:Special:FilePath/Pathwidth-1_obstructions.svg wiki-commons:Special:FilePath/Pathwidth.jpg wiki-commons:Special:FilePath/Interval_graph.svg
foaf:isPrimaryTopicOf	wikipedia-en:Pathwidth
is dbo:wikiPageDisambiguates of	dbr:Width_(disambiguation)
is dbo:wikiPageRedirects of	dbr:Path-width dbr:Path_Decomposition dbr:Path_decomposition
is dbo:wikiPageWikiLink of	dbr:S2S_(mathematics) dbr:Glossary_of_graph_theory dbr:Tree_decomposition dbr:List_of_NP-complete_problems dbr:Strahler_number dbr:Interval_graph dbr:Caterpillar_tree dbr:Graph_bandwidth dbr:Graph_structure_theorem dbr:Clique-sum dbr:Robertson–Seymour_theorem dbr:Graph_minor dbr:Cubic_graph dbr:Indifference_graph dbr:Pursuit–evasion dbr:Tree-depth dbr:List_of_unsolved_problems_in_mathematics dbr:Apex_graph dbr:Treewidth dbr:Degeneracy_(graph_theory) dbr:Permutation_graph dbr:Chordal_completion dbr:Layered_graph_drawing dbr:Universal_point_set dbr:Unknotting_problem dbr:GNRS_conjecture dbr:Cutwidth dbr:Width_(disambiguation) dbr:Path-width dbr:Path_Decomposition dbr:Path_decomposition
is foaf:primaryTopic of	wikipedia-en:Pathwidth