An efficient algorithm to solve the conditional covering problem on trapezoid graphs (Q410643): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 5 users not shown) | |||
Property / review text | |||
Summary: Let \(G = (V, E)\) be a simple connected undirected graph. Each vertex \(v \in V\) has a cost \(c(v)\) and provides a positive coverage radius \(R(v)\). A distance \(d_{uv}\) is associated with each edge \(\{u, v\} \in E\), and \(d(u, v)\) is the shortest distance between every pair of vertices \(u, v \in V\). A vertex \(v\) can cover all vertices that lie within the distance \(R(v)\), except the vertex itself. The conditional covering problem is to minimize the sum of the costs required to cover all the vertices in \(G\). This problem is NP-complete for general graphs, even it remains NP-complete for chordal graphs. In this paper, an \(O(n^2)\) time algorithm to solve a special case of the problem in a trapezoid graph is proposed, where \(n\) is the number of vertices of the graph. In this special case, \(d_{uv} = 1\) for every edge \(\{u, v\} \in E, c(v) = c\) for every \(v \in V(G)\), and \(R(v) = R\), an integer >1, for every \(v \in V(G)\). A new data structure on trapezoid graphs is used to solve the problem. | |||
Property / review text: Summary: Let \(G = (V, E)\) be a simple connected undirected graph. Each vertex \(v \in V\) has a cost \(c(v)\) and provides a positive coverage radius \(R(v)\). A distance \(d_{uv}\) is associated with each edge \(\{u, v\} \in E\), and \(d(u, v)\) is the shortest distance between every pair of vertices \(u, v \in V\). A vertex \(v\) can cover all vertices that lie within the distance \(R(v)\), except the vertex itself. The conditional covering problem is to minimize the sum of the costs required to cover all the vertices in \(G\). This problem is NP-complete for general graphs, even it remains NP-complete for chordal graphs. In this paper, an \(O(n^2)\) time algorithm to solve a special case of the problem in a trapezoid graph is proposed, where \(n\) is the number of vertices of the graph. In this special case, \(d_{uv} = 1\) for every edge \(\{u, v\} \in E, c(v) = c\) for every \(v \in V(G)\), and \(R(v) = R\), an integer >1, for every \(v \in V(G)\). A new data structure on trapezoid graphs is used to solve the problem. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C85 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C12 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05B40 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6021215 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
data structure on trapezoid graphs | |||
Property / zbMATH Keywords: data structure on trapezoid graphs / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.5402/2011/213084 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2155274708 / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q58689078 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Dynamic programming algorithms for the conditional covering problem on path and extended star graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3797233 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Trapezoid graphs and their coloring / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the structure of trapezoid graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the 2-Chain Subgraph Cover and Related Problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An Analysis of Network Location Problems with Distance Constraints / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: New heuristics for the conditional covering problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Conditional covering: greedy heuristics and computational results / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Facility location on a tree with maximum distance constraints / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A dynamic programming algorithm for the conditional covering problem on tree graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algorithms for solving the conditional covering problem on paths / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On conditional covering problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3171770 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Chaining algorithms for multiple genome comparison / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3328583 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 01:45, 5 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An efficient algorithm to solve the conditional covering problem on trapezoid graphs |
scientific article |
Statements
An efficient algorithm to solve the conditional covering problem on trapezoid graphs (English)
0 references
3 April 2012
0 references
Summary: Let \(G = (V, E)\) be a simple connected undirected graph. Each vertex \(v \in V\) has a cost \(c(v)\) and provides a positive coverage radius \(R(v)\). A distance \(d_{uv}\) is associated with each edge \(\{u, v\} \in E\), and \(d(u, v)\) is the shortest distance between every pair of vertices \(u, v \in V\). A vertex \(v\) can cover all vertices that lie within the distance \(R(v)\), except the vertex itself. The conditional covering problem is to minimize the sum of the costs required to cover all the vertices in \(G\). This problem is NP-complete for general graphs, even it remains NP-complete for chordal graphs. In this paper, an \(O(n^2)\) time algorithm to solve a special case of the problem in a trapezoid graph is proposed, where \(n\) is the number of vertices of the graph. In this special case, \(d_{uv} = 1\) for every edge \(\{u, v\} \in E, c(v) = c\) for every \(v \in V(G)\), and \(R(v) = R\), an integer >1, for every \(v \in V(G)\). A new data structure on trapezoid graphs is used to solve the problem.
0 references
data structure on trapezoid graphs
0 references
0 references