Discrete Applied Mathematics, ISSN 0166-218X, 02/2018, Volume 236, pp. 395 - 407

... for t>3, while the complexity status of this problem is unresolved when t=3. For every t>2 and b>0, an efficient dynamic programming algorithm to decide tree t-spanner admissibility of graphs with vertex degrees less than b is presented...

Tree spanner | Bounded degree graph | Efficient graph algorithm | Spanning tree | Distance | MATHEMATICS, APPLIED | COMPLEXITY

Tree spanner | Bounded degree graph | Efficient graph algorithm | Spanning tree | Distance | MATHEMATICS, APPLIED | COMPLEXITY

Journal Article

Discrete Applied Mathematics, ISSN 0166-218X, 10/2018, Volume 248, pp. 93 - 101

.... We prove that Square Root is O(n)-time solvable for graphs of maximum degree 5 and O(n4)-time solvable for graphs of maximum degree at most 6.

Square root | Polynomial algorithm | Bounded degree graph | MATHEMATICS, APPLIED | SPLIT GRAPHS | LOGIC | Computer Science | Computational Complexity

Square root | Polynomial algorithm | Bounded degree graph | MATHEMATICS, APPLIED | SPLIT GRAPHS | LOGIC | Computer Science | Computational Complexity

Journal Article

SIAM Journal on Discrete Mathematics, ISSN 0895-4801, 2014, Volume 28, Issue 3, pp. 1467 - 1478

...) be the family of all graphs on n vertices with maximum degree at most d. Dellamonica, Kohayakawa, Rodl, and Rucinski...

Universal graphs | Graph embedding | Universality | Random graphs | Containment problem | Bounded degree graphs | universality | EXISTENCE | MATHEMATICS, APPLIED | containment problem | bounded degree graphs | CONTAIN | graph embedding | random graphs | universal graphs | Constants | Graphs | Algorithms | Upper bounds | Mathematical analysis | Density

Universal graphs | Graph embedding | Universality | Random graphs | Containment problem | Bounded degree graphs | universality | EXISTENCE | MATHEMATICS, APPLIED | containment problem | bounded degree graphs | CONTAIN | graph embedding | random graphs | universal graphs | Constants | Graphs | Algorithms | Upper bounds | Mathematical analysis | Density

Journal Article

Algorithmica, ISSN 1432-0541, 2015, Volume 75, Issue 2, pp. 363 - 382

.... In the context of graph isomorphism, we define triviality to mean a graph with maximum degree bounded by a constant, as such graph classes admit polynomial-time isomorphism tests...

Theory of Computation | Graph theory | Fixed-parameter tractable | Bounded degree | Complexity theory | Tree-depth | Computer Systems Organization and Communication Networks | Data Structures, Cryptology and Information Theory | Algorithms | Graph | Mathematics of Computing | Computer Science | Isomorphism | Canonization | Algorithm Analysis and Problem Complexity | Parameterized complexity | COMPUTER SCIENCE, SOFTWARE ENGINEERING | MATHEMATICS, APPLIED

Theory of Computation | Graph theory | Fixed-parameter tractable | Bounded degree | Complexity theory | Tree-depth | Computer Systems Organization and Communication Networks | Data Structures, Cryptology and Information Theory | Algorithms | Graph | Mathematics of Computing | Computer Science | Isomorphism | Canonization | Algorithm Analysis and Problem Complexity | Parameterized complexity | COMPUTER SCIENCE, SOFTWARE ENGINEERING | MATHEMATICS, APPLIED

Journal Article

Journal of Combinatorial Theory, Series B, ISSN 0095-8956, 01/2019, Volume 134, pp. 179 - 202

.... This solves a problem of Conlon, Fox, Lee, and Sudakov. On the other hand, we prove that every graph G on n vertices with maximum degree 2 admits an ordering G of G such that R‾(G) is linear in n...

Ordered Ramsey number | Ramsey number | Bounded degree | Ordered graph | MATHEMATICS

Ordered Ramsey number | Ramsey number | Bounded degree | Ordered graph | MATHEMATICS

Journal Article

Algorithmica, ISSN 1432-0541, 2014, Volume 73, Issue 1, pp. 1 - 20

We present an efficient algorithm for testing outerplanarity of graphs in the bounded-degree model...

Computer Systems Organization and Communication Networks | Data Structures, Cryptology and Information Theory | Algorithms | Mathematics of Computing | Computer Science | Property testing | Outerplanarity | Theory of Computation | Algorithm Analysis and Problem Complexity | Bounded-degree model | COMPUTER SCIENCE, SOFTWARE ENGINEERING | MATHEMATICS, APPLIED | Models

Computer Systems Organization and Communication Networks | Data Structures, Cryptology and Information Theory | Algorithms | Mathematics of Computing | Computer Science | Property testing | Outerplanarity | Theory of Computation | Algorithm Analysis and Problem Complexity | Bounded-degree model | COMPUTER SCIENCE, SOFTWARE ENGINEERING | MATHEMATICS, APPLIED | Models

Journal Article

SIAM journal on discrete mathematics, ISSN 1095-7146, 2017, Volume 31, Issue 1, pp. 155 - 171

We show that for any fixed dense graph G and bounded-degree tree T on the same number of vertices, a modest random perturbation of G will typically contain a copy...

Smoothed analysis | Random graphs | Bounded-degree spanning trees | DENSE | MATHEMATICS, APPLIED | RANDOM EDGES | smoothed analysis | bounded-degree spanning trees | random graphs | SUBGRAPHS | BANDWIDTH

Smoothed analysis | Random graphs | Bounded-degree spanning trees | DENSE | MATHEMATICS, APPLIED | RANDOM EDGES | smoothed analysis | bounded-degree spanning trees | random graphs | SUBGRAPHS | BANDWIDTH

Journal Article

Information and computation, ISSN 0890-5401, 2008, Volume 206, Issue 11, pp. 1264 - 1275

... (connected, total, independent) in bounded degree graphs. Asymptotically, for degree bound approaching infinity, these bounds almost match the known upper bounds...

MATHEMATICS, APPLIED | COMPUTER SCIENCE, THEORY & METHODS | Mechanical properties | Algorithms | Universities and colleges | Hardness

MATHEMATICS, APPLIED | COMPUTER SCIENCE, THEORY & METHODS | Mechanical properties | Algorithms | Universities and colleges | Hardness

Journal Article

SIAM Journal on Discrete Mathematics, ISSN 0895-4801, 2015, Volume 29, Issue 1, pp. 59 - 64

...). In this article, we focus on bounded degree graphs and show that the separation dimension of a graph with maximum degree d is at most 2(9) (log*d)d. We also demonstrate that the above bound is nearly tight by showing that, for every d, almost all d-regular graphs have separation dimension at least [d/2]

Bounded degree | Boxicity | Linegraph | Separation dimension | MATHEMATICS, APPLIED | bounded degree | separation dimension | boxicity | linegraph | SETS

Bounded degree | Boxicity | Linegraph | Separation dimension | MATHEMATICS, APPLIED | bounded degree | separation dimension | boxicity | linegraph | SETS

Journal Article

Random structures & algorithms, ISSN 1042-9832, 2018, Volume 53, Issue 4, pp. 604 - 637

A graph is said to be H(n,Δ) ‐universal if it contains every graph with n vertices and maximum degree at most Δ as a subgraph...

universality | Random graphs | spanning subgraphs | COMPUTER SCIENCE, SOFTWARE ENGINEERING | MATHEMATICS | MATHEMATICS, APPLIED | THRESHOLD | TREES | BOUNDED DEGREE | HYPERGRAPHS | SUBGRAPHS | Graphs | Embedding | Graph theory

universality | Random graphs | spanning subgraphs | COMPUTER SCIENCE, SOFTWARE ENGINEERING | MATHEMATICS | MATHEMATICS, APPLIED | THRESHOLD | TREES | BOUNDED DEGREE | HYPERGRAPHS | SUBGRAPHS | Graphs | Embedding | Graph theory

Journal Article

Science China Mathematics, ISSN 1674-7283, 7/2016, Volume 59, Issue 7, pp. 1427 - 1440

.... We consider some generalized acyclic k-colorings, namely, we require that each color class induces an acyclic or bounded degree graph...

acyclic coloring | Mathematics | Applications of Mathematics | bounded degree graph | computational complexity | 05C15 | MATHEMATICS | MATHEMATICS, APPLIED | IMPROPER COLORINGS | Computer science | Algorithms | Coloring | Graphs | Graph theory | Mathematical analysis

acyclic coloring | Mathematics | Applications of Mathematics | bounded degree graph | computational complexity | 05C15 | MATHEMATICS | MATHEMATICS, APPLIED | IMPROPER COLORINGS | Computer science | Algorithms | Coloring | Graphs | Graph theory | Mathematical analysis

Journal Article

Information and Computation, ISSN 0890-5401, 08/2015, Volume 243, pp. 75 - 85

We present a number of exponential-time algorithms for problems in sparse matrices and graphs of bounded average degree...

Moderately-exponential algorithms | Minimum weight Hamiltonian cycle | Bounded average degree | Counting perfect matchings | MATHEMATICS, APPLIED | SALESMAN PROBLEM | SAT | PERMANENTS | HARD | COMPUTER SCIENCE, THEORY & METHODS | Algorithms

Moderately-exponential algorithms | Minimum weight Hamiltonian cycle | Bounded average degree | Counting perfect matchings | MATHEMATICS, APPLIED | SALESMAN PROBLEM | SAT | PERMANENTS | HARD | COMPUTER SCIENCE, THEORY & METHODS | Algorithms

Journal Article

Algorithmica, ISSN 0178-4617, 10/2018, Volume 80, Issue 10, pp. 2834 - 2848

A linear ordering of the vertices of a graph G separates two edges of G if both the endpoints of one precede both the endpoints of the other in the order. We call two edges $$\{a,b\}$$ {a,b} and $$\{c,d\}$$ {c,d...

05C75 | Asteroidal triples | Vertex ordering | 05C85 | 05C62 | Theory of Computation | Acyclic orientation | Computer Systems Organization and Communication Networks | Data Structures, Cryptology and Information Theory | Algorithms | Mathematics of Computing | Induced separation dimension | Computer Science | Algorithm Analysis and Problem Complexity | INDUCED MATCHINGS | INTERSECTION GRAPHS | MATHEMATICS, APPLIED | NUMBER | BOUNDED DEGREE | HYPERGRAPHS | INDEPENDENT SETS | COMPUTER SCIENCE, SOFTWARE ENGINEERING | 2K-FREE GRAPHS

05C75 | Asteroidal triples | Vertex ordering | 05C85 | 05C62 | Theory of Computation | Acyclic orientation | Computer Systems Organization and Communication Networks | Data Structures, Cryptology and Information Theory | Algorithms | Mathematics of Computing | Induced separation dimension | Computer Science | Algorithm Analysis and Problem Complexity | INDUCED MATCHINGS | INTERSECTION GRAPHS | MATHEMATICS, APPLIED | NUMBER | BOUNDED DEGREE | HYPERGRAPHS | INDEPENDENT SETS | COMPUTER SCIENCE, SOFTWARE ENGINEERING | 2K-FREE GRAPHS

Journal Article

Theory of Computing Systems, ISSN 1432-4350, 5/2013, Volume 52, Issue 4, pp. 687 - 718

We consider the Partition Into Triangles problem on bounded degree graphs. We show that this problem is polynomial-time solvable on graphs of maximum degree three by giving a linear-time algorithm...

Computational Mathematics and Numerical Analysis | Algorithms | Partition into triangles | Computer Science | Bounded degree graphs | Theory of Computation | Graph algorithms | Satisfiability | Exact algorithms | MATHEMATICS | NUMBER | EXACT SATISFIABILITY | COMPUTER SCIENCE, THEORY & METHODS | Computer science | Studies | Analysis | Graph theory | Polynomials | Graphs | Partitions | Computation | Triangles

Computational Mathematics and Numerical Analysis | Algorithms | Partition into triangles | Computer Science | Bounded degree graphs | Theory of Computation | Graph algorithms | Satisfiability | Exact algorithms | MATHEMATICS | NUMBER | EXACT SATISFIABILITY | COMPUTER SCIENCE, THEORY & METHODS | Computer science | Studies | Analysis | Graph theory | Polynomials | Graphs | Partitions | Computation | Triangles

Journal Article

Random structures & algorithms, ISSN 1042-9832, 2017, Volume 50, Issue 3, pp. 380 - 393

A graph G is said to be ℋ(n,Δ)‐universal if it contains every graph on at most n vertices with maximum degree at most Δ...

universality | bounded degree graphs | random graphs | COMPUTER SCIENCE, SOFTWARE ENGINEERING | MATHEMATICS | MATHEMATICS, APPLIED | TREES | BOUNDED-DEGREE | Graphs | Algorithms | Asymptotic properties | Graph theory | Boundaries | Bypasses | Number theory

universality | bounded degree graphs | random graphs | COMPUTER SCIENCE, SOFTWARE ENGINEERING | MATHEMATICS | MATHEMATICS, APPLIED | TREES | BOUNDED-DEGREE | Graphs | Algorithms | Asymptotic properties | Graph theory | Boundaries | Bypasses | Number theory

Journal Article

Combinatorica, ISSN 0209-9683, 10/2016, Volume 36, Issue 5, pp. 537 - 556

For a positive integer m, let f(m) be the maximum value t such that any graph with m edges has a bipartite subgraph of size at least t, and let g(m...

Mathematics, general | Mathematics | Combinatorics | 05C35 | MATHEMATICS | MAX-CUT | K-PARTITIONS | SUBGRAPHS | IMPROVED APPROXIMATION | BOUNDED-DEGREE

Mathematics, general | Mathematics | Combinatorics | 05C35 | MATHEMATICS | MAX-CUT | K-PARTITIONS | SUBGRAPHS | IMPROVED APPROXIMATION | BOUNDED-DEGREE

Journal Article

SIAM journal on computing, ISSN 1095-7111, 2009, Volume 38, Issue 6, pp. 2499 - 2510

We study graph properties that are testable for bounded-degree graphs in time independent of the input size...

Planar graphs | Property testing | Approximation algorithms | Hereditary graph properties | Randomized algorithms | Nonexpanding graphs | Bounded-degree graphs | MATHEMATICS, APPLIED | planar graphs | randomized algorithms | SEPARATOR THEOREM | nonexpanding graphs | bounded-degree graphs | COMPUTER SCIENCE, THEORY & METHODS | property testing | hereditary graph properties | approximation algorithms

Planar graphs | Property testing | Approximation algorithms | Hereditary graph properties | Randomized algorithms | Nonexpanding graphs | Bounded-degree graphs | MATHEMATICS, APPLIED | planar graphs | randomized algorithms | SEPARATOR THEOREM | nonexpanding graphs | bounded-degree graphs | COMPUTER SCIENCE, THEORY & METHODS | property testing | hereditary graph properties | approximation algorithms

Journal Article

Theoretical Computer Science, ISSN 0304-3975, 2012, Volume 418, pp. 92 - 105

.... However, before construction of DBMST, it is NP-hard to determine whether or not there is a degree- k spanning tree for an arbitrary graph, where k is 3 or 4...

Wireless sensor network | Degree-bounded minimum spanning tree | Necessary condition | Unit disk graph | COMPUTER SCIENCE, THEORY & METHODS | WEIGHT | Analysis | Algorithms

Wireless sensor network | Degree-bounded minimum spanning tree | Necessary condition | Unit disk graph | COMPUTER SCIENCE, THEORY & METHODS | WEIGHT | Analysis | Algorithms

Journal Article

Theoretical Computer Science, ISSN 0304-3975, 07/2015, Volume 590, pp. 86 - 95

A homomorphism from a graph G to a graph H is locally bijective, surjective, or injective if its restriction to the neighborhood of every vertex of G is bijective, surjective, or injective, respectively...

Locally constrained graph homomorphisms | Bounded treewidth | Bounded degree | Computational complexity | COMPUTATIONAL-COMPLEXITY | REGULAR GRAPHS | ASSIGNMENT | CLASSIFICATION | COVERINGS | NETWORKS | COMPUTER SCIENCE, THEORY & METHODS | Hardness | Constrictions | Homomorphisms | Graphs | Complement | Constraints

Locally constrained graph homomorphisms | Bounded treewidth | Bounded degree | Computational complexity | COMPUTATIONAL-COMPLEXITY | REGULAR GRAPHS | ASSIGNMENT | CLASSIFICATION | COVERINGS | NETWORKS | COMPUTER SCIENCE, THEORY & METHODS | Hardness | Constrictions | Homomorphisms | Graphs | Complement | Constraints

Journal Article

Discrete Applied Mathematics, ISSN 0166-218X, 2011, Volume 159, Issue 17, pp. 1947 - 1953

... ] induced by the vertices of V 1 has maximum degree at most k and the graph G [ V 2 ] induced by the vertices of V 2 has maximum degree at most j...

Subgraphs with bounded maximum degree | Linear programming | Vertex partition | Discharging procedure | Maximum average degree | COLORINGS | MATHEMATICS, APPLIED | EVERY PLANAR MAP | Mathematical analysis | Graphs | Computer Science | Discrete Mathematics

Subgraphs with bounded maximum degree | Linear programming | Vertex partition | Discharging procedure | Maximum average degree | COLORINGS | MATHEMATICS, APPLIED | EVERY PLANAR MAP | Mathematical analysis | Graphs | Computer Science | Discrete Mathematics

Journal Article

No results were found for your search.

Cannot display more than 1000 results, please narrow the terms of your search.