Name
Abstract | ||
|---|---|---|
Consider the decision problem STRICT BOUNDED CIRCUIT INTERSECTION (SBCI): Given a finite graph G =( V , E ) and K ∈ Z + . Is there a subset E ′ ⊆ E with | E ′| ⩾ K such that | E ′ ∩ C | < | C |/ L for every circuit C of G ? The problem NONSTRICT BCI (NBCI) is the same, except that | E ′ ∩ C | < | C |/ L is replaced by | E ′ ∩ C | ⩽ | C |/ L . It is proved that SBCI is NP-complete for every fixed integer L ⩾2 even if G is planar and bipartite, and NBCI is NP-complete for every fixed integer L ⩾ 3 even if G is planar. For every fixed integer L ⩾ 4, NBCI is NP-complete even if G is planar and bipartite. The case L = 2 of SBCI answers a question of Welsh, stemming from knot theory. The case L = 2 of NBCI, motivated by coding theory, has been shown to be polynomial for every graph by Frank. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1016/0012-365X(93)E0194-9 | Discrete Mathematics |
Keywords | Field | DocType |
circuit intersection,coding theory,knot theory,decision problem | Integer,Graph,Discrete mathematics,Combinatorics,Polynomial,Bipartite graph,Knot theory,Coding theory,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
141 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
1 | 0.37 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aviezri S. Fraenkel | 1 | 559 | 164.51 |
| Martin Loebl | 2 | 152 | 28.66 |