Now showing items 1-5 of 5

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

(2002-05)
External research report
Open Access
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 ...
• #### Bidimensional parameters and local treewidth ﻿

(2003-10)
External research report
Open Access
For several graph theoretic parameters such as vertex cover and dominating set, it is known that if their values are bounded by k then the treewidth of the graph is bounded by some function of k. This fact is used as the ...
• #### Exponential speedup of fixed parameter algorithms on K_{3,3}-minor-free or K_{5}-minor-free graphs ﻿

(2002-03)
External research report
Open Access
We present a fixed parameter algorithm that constructively solves the k-dominating set problem on graphs excluding one of the K_{5} or K_3,3 as a minor in time O(3^{6sqrt{34 k}}n^{O(1)}). In fact, we present our ...
• #### Fast approximation schemes for K_{3,3}-minor-free or K_{5}-minor-free graphs ﻿

(2002-05)
External research report
Open Access
As the class of graphs of bounded treewidth is of limited size, we need to solve NP-hard problems for wider classes of graphs than this class. Eppstein introduced a new concept which can be considered as a generalization ...
• #### Fixed-parameter algorithms for the (k,r)-center in planar graphs and map graphs ﻿

(2003-09)
External research report
Open Access
The (k,r)-center problem} asks whether an input graph G has atr most k vertices (called centers) such that every vertex of \$ is within distance at most r from some center. In this paper we prove that the (k,r)-center ...
{"extraction_info": {"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8040605783462524, "perplexity": 1938.5230953503726}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2021-31/segments/1627046153491.18/warc/CC-MAIN-20210727202227-20210727232227-00013.warc.gz"}