article

Free access

Covering edges by cliques with regard to keyword conflicts and intersection graphs

Authors:

L. T. Kou,

L. J. Stockmeyer,

C. K. WongAuthors Info & Claims

Communications of the ACM, Volume 21, Issue 2

Pages 135 - 139

https://doi.org/10.1145/359340.359346

Published: 01 February 1978 Publication History

PDF eReader

Abstract

Kellerman has presented a method for determining keyword conflicts and described a heuristic algorithm which solves a certain combinatorial optimization problem in connection with this method. This optimization problem is here shown to be equivalent to the problem of covering the edges of a graph by complete subgraphs with the objective of minimizing the number of complete subgraphs. A relationship between this edge-clique-cover problem and the graph coloring problem is established which allows algorithms for either one of these problems to be constructed from algorithms for the other. As consequences of this relationship, the keyword conflict problem and the edge-clique-cover problem are shown to be NP-complete, and if P ≠ NP then they do not admit polynomial-time approximation algorithms which always produce solutions within a factor less than 2 from the optimum.

References

[1]

Aho, A.V., Hopcroft, J.E., and Ullman, J.D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974, chap. 10.

Digital Library

Google Scholar

[2]

Garey, M.R., and Johnson, D.S. The complexity of nearoptimal graph coloring. J.ACM 23, 1 (Jan. 1976), 43-49.

Digital Library

Google Scholar

[3]

Harary, F. Graph Theory. Addison-Wesley, Reading, Mass., 1969.

Google Scholar

[4]

Harary, F. On the Intersection Number of a Graph. In Proof Techniques in Graph Theory, F. Harary, Ed., Academic Press, New York, 1969, pp. 71-72.

Google Scholar

[5]

Johnson, D.S. Worst case behavior of graph coloring algorithms. Proc. Fifth Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Utilitas Mathcmatica Pub., Winnipeg, Canada, 1974, pp. 513-528.

Google Scholar

[6]

Johnson, D.S. Approximation algorithms for combinatorial problems. J. Comptr. Syst. Sci. 9(1974), 256-278.

Digital Library

Google Scholar

[7]

Karp, R.M. On the computational complexity of combinatorial problems. Networks 5 (1975), 45-68.

Digital Library

Google Scholar

[8]

Kellerman, E. Determination of keyword conflict. IBM Tech. Disclosure Bull. 16, 2 (July 1973), 544-546.

Google Scholar

[9]

Welsh, D.J.A., and Powell, M.B. An upper bound to the chromatic number of a graph and its application to time tabling problems. Comptr. J. 10 (1967), 85-86.

Crossref

Google Scholar

[10]

Wood, D.C. A technique for coloring a graph applicable to large scale time-tabling problems. Comptr. J. 12 (1969), 317-319.

Crossref

Google Scholar

Cited By

View all

Bärmann AMartin AStaszek J(2024)A decomposition approach for integrated locomotive scheduling and driver assignment in rail freight transportEURO Journal on Transportation and Logistics10.1016/j.ejtl.2024.10014513(100145)Online publication date: 2024
https://doi.org/10.1016/j.ejtl.2024.100145
Bai YCortés PNaserasr RQuiroz D(2024)Characterizing and recognizing exact-distance squares of graphsDiscrete Mathematics10.1016/j.disc.2023.113493347:8(113493)Online publication date: Aug-2024
https://doi.org/10.1016/j.disc.2023.113493
Guo HPatton KWarnke L(2023)Prague Dimension of Random GraphsCombinatorica10.1007/s00493-023-00016-943:5(853-884)Online publication date: 6-Sep-2023
https://dl.acm.org/doi/10.1007/s00493-023-00016-9
Show More Cited By

Index Terms

Covering edges by cliques with regard to keyword conflicts and intersection graphs

Recommendations

The complexity of clique graph recognition

A complete set of a graph G is a subset of vertices inducing a complete subgraph. A clique is a maximal complete set. Denote by C(G) the clique family of G. The clique graph of G, denoted by K(G), is the intersection graph of C(G). Say that G is a ...
On the structure of certain intersection graphs

Recently Gavril introduced a new class of intersection graphs called interval-filament graphs. These include co-comparability graphs and polygon-circle graphs (the intersection graphs of polygons inscribed in a circle), which include circular-arc graphs ...
The k-edge intersection graphs of paths in a tree

We consider a generalization of edge intersection graphs of paths in a tree. Let P be a collection of nontrivial simple paths in a tree T. We define the k-edge (k>=1) intersection graph @C"k(P), whose vertices correspond to the members of P, and two ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 21, Issue 2

Feb. 1978

74 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/359340

Editor:
Robert L. Ashenhurst
The Univ. of Chicago, Chicago, IL

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 February 1978

Published in CACM Volume 21, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

87
Total Citations
View Citations
1,107
Total Downloads

Downloads (Last 12 months)189
Downloads (Last 6 weeks)46

Reflects downloads up to 16 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bärmann AMartin AStaszek J(2024)A decomposition approach for integrated locomotive scheduling and driver assignment in rail freight transportEURO Journal on Transportation and Logistics10.1016/j.ejtl.2024.10014513(100145)Online publication date: 2024
https://doi.org/10.1016/j.ejtl.2024.100145
Bai YCortés PNaserasr RQuiroz D(2024)Characterizing and recognizing exact-distance squares of graphsDiscrete Mathematics10.1016/j.disc.2023.113493347:8(113493)Online publication date: Aug-2024
https://doi.org/10.1016/j.disc.2023.113493
Guo HPatton KWarnke L(2023)Prague Dimension of Random GraphsCombinatorica10.1007/s00493-023-00016-943:5(853-884)Online publication date: 6-Sep-2023
https://dl.acm.org/doi/10.1007/s00493-023-00016-9
Schwartz S(2022)An overview of graph covering and partitioningDiscrete Mathematics10.1016/j.disc.2022.112884345:8Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1016/j.disc.2022.112884
Holm DMikkelsen RSørensen MStidsen T(2022)A graph-based MIP formulation of the International Timetabling Competition 2019Journal of Scheduling10.1007/s10951-022-00724-y25:4(405-428)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1007/s10951-022-00724-y
Abdullah WHossain S(2022)A Sparse Matrix Approach for Covering Large Complex Networks by CliquesComputational Science – ICCS 202210.1007/978-3-031-08757-8_43(505-517)Online publication date: 15-Jun-2022
https://doi.org/10.1007/978-3-031-08757-8_43
Caucchiolo ACicalese F(2022)On the Intractability Landscape of Digraph Intersection RepresentationsCombinatorial Algorithms10.1007/978-3-031-06678-8_20(270-284)Online publication date: 7-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-06678-8_20
Tambieva DShmatko SShlaev D(2022)Elements of Fuzzy Logic in Solving Clustering ProblemsMathematics and its Applications in New Computer Systems10.1007/978-3-030-97020-8_32(347-356)Online publication date: 26-Apr-2022
https://doi.org/10.1007/978-3-030-97020-8_32
Burgio GArenas AGómez SMatamalas J(2021)Network clique cover approximation to analyze complex contagions through group interactionsCommunications Physics10.1038/s42005-021-00618-z4:1Online publication date: 31-May-2021
https://doi.org/10.1038/s42005-021-00618-z
Rodrigues M(2021)Fast constructive and improvement heuristics for edge clique coveringDiscrete Optimization10.1016/j.disopt.2021.10062839(100628)Online publication date: Feb-2021
https://doi.org/10.1016/j.disopt.2021.100628
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

The complexity of clique graph recognition

On the structure of certain intersection graphs

The k-edge intersection graphs of paths in a tree

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations