X
Search Filters
Format Format
Subjects Subjects
Subjects Subjects
X
Sort by Item Count (A-Z)
Filter by Count
computer science (19) 19
algorithms (13) 13
algorithm analysis and problem complexity (9) 9
mathematics, applied (9) 9
reconfiguration (9) 9
calculating (8) 8
computing (8) 8
counting (8) 8
dynamic programming (8) 8
electric digital data processing (8) 8
mathematics (8) 8
physics (8) 8
computer science, theory & methods (7) 7
discrete mathematics in computer science (7) 7
computer science - data structures and algorithms (6) 6
data structures (6) 6
algorithm (5) 5
computer communication networks (5) 5
graph algorithms (5) 5
graphs (5) 5
numeric computing (5) 5
planar graph (5) 5
studies (5) 5
approximation algorithm (4) 4
computer science - computational complexity (4) 4
discrete mathematics and combinatorics (4) 4
logics and meanings of programs (4) 4
maximum leaf (4) 4
sparsest cut (4) 4
theoretical computer science (4) 4
theory of computation (4) 4
approximation (3) 3
colour graph (3) 3
computational complexity (3) 3
computer graphics (3) 3
computer systems organization and communication networks (3) 3
connected dominating set (3) 3
cubic graph (3) 3
electronic and computer engineering (3) 3
engineering, electrical & electronic (3) 3
management of computing and information systems (3) 3
multimedia information systems (3) 3
polynomials (3) 3
shortest path (3) 3
spanning tree (3) 3
telecommunications (3) 3
user interfaces and human computer interaction (3) 3
agent (2) 2
circle graph (2) 2
claw-free graph (2) 2
clique-width (2) 2
coloring (2) 2
colour refinement (2) 2
community (2) 2
computation by abstract devices (2) 2
computational theory and mathematics (2) 2
computer science - discrete mathematics (2) 2
computer science, software engineering (2) 2
counting problem (2) 2
data structures, cryptology and information theory (2) 2
decomposable graphs (2) 2
directed trees (2) 2
ecosystem (2) 2
emergence (2) 2
evolution (2) 2
fullerene (2) 2
fusene (2) 2
graph (2) 2
graph classes (2) 2
graph coloring (2) 2
graph isomorphism (2) 2
graph theory (2) 2
group (2) 2
hexagonal patch (2) 2
matching immune (2) 2
matching-cut (2) 2
mathematics of computing (2) 2
maximum weight independent set (2) 2
mobile agent system (2) 2
multi agent system (2) 2
partition refinement (2) 2
polyhex (2) 2
polynomial time (2) 2
pspace-complete (2) 2
reconfiguration problem (2) 2
rerouting (2) 2
resource allocation (2) 2
strong np-hardness (2) 2
superpolynomial distance (2) 2
trees (2) 2
treewidth (2) 2
unsplittable flow (2) 2
vertex-recolouring (2) 2
algorithm design and analysis (1) 1
analysis of algorithms (1) 1
applied mathematics (1) 1
approximability (1) 1
approximation algorithms (1) 1
approximation methods (1) 1
apx-hard (1) 1
more...
Language Language
Publication Date Publication Date
Click on a bar to filter by decade
Slide to change publication date range


Discrete Applied Mathematics, ISSN 0166-218X, 11/2017, Volume 231, pp. 95 - 112
A rerouting sequence is a sequence of shortest st-paths such that consecutive paths differ in one vertex. We study the Shortest Path Rerouting Problem, which... 
Shortest path | Reconfiguration problem | Rerouting | Dynamic programming | Planar graph | Polynomial time | COLORINGS | MATHEMATICS, APPLIED | RECONFIGURATION
Journal Article
Journal of Graph Theory, ISSN 0364-9024, 10/2016, Volume 83, Issue 2, pp. 164 - 195
We study the following independent set reconfiguration problem, called TAR‐Reachability: given two independent sets I and J of a graph G, both of size at least... 
dynamic programming | reconfiguration | efficient algorithm | graph classes | graph decomposition | GRAPH | MATHEMATICS | SHORTEST PATHS | COMPLEXITY | ALGORITHM | Algorithms
Journal Article
Theoretical Computer Science, ISSN 0304-3975, 10/2013, Volume 510, pp. 1 - 12
The Shortest Path Reconfiguration problem has as input a graph G with unit edge lengths, with vertices s and t, and two shortest st-paths P and Q. The question... 
Shortest path | Chordal graph | PSPACE-hard | Claw-free graph | Reconfiguration | Reachability | METIS-302544 | EWI-23842 | IR-89578 | COMPUTER SCIENCE, THEORY & METHODS | Algorithms
Journal Article
Acta Informatica, ISSN 0001-5903, 11/2019, Volume 56, Issue 7, pp. 619 - 648
Journal Article
Journal of Discrete Algorithms, ISSN 1570-8667, 04/2012, Volume 12, pp. 14 - 23
We consider the problem of finding a spanning tree with maximum number of leaves. A 2-approximation algorithm is known for this problem, and a... 
Maximum leaf | Minimum connected dominating set | APX-hard | Approximation algorithm | Cubic graph | Algorithms
Journal Article
Theoretical Computer Science, ISSN 0304-3975, 2009, Volume 410, Issue 50, pp. 5215 - 5226
Suppose we are given a graph G together with two proper vertex k -colourings of G , α and β . How easily can we decide whether it is possible to transform α... 
Colour graph | PSPACE-complete | Vertex-recolouring | Superpolynomial distance | COMPUTER SCIENCE, THEORY & METHODS
Journal Article
Leibniz International Proceedings in Informatics, LIPIcs, ISSN 1868-8969, 2012, Volume 18, pp. 337 - 349
Conference Proceeding
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743, 2012, Volume 7464, pp. 222 - 233
Conference Proceeding
Algorithmica, ISSN 0178-4617, 2/2017, Volume 77, Issue 2, pp. 374 - 388
Journal Article
Theory of Computing Systems, ISSN 1432-4350, 5/2017, Volume 60, Issue 4, pp. 581 - 614
An assignment of colours to the vertices of a graph is stable if any two vertices of the same colour have identically coloured neighbourhoods. The goal of... 
Computational Mathematics and Numerical Analysis | Graph isomorphism | Computer Science | Partition refinement | Theory of Computation | Colour refinement | Canonical labelling | GRAPH | MATHEMATICS | COMPUTER SCIENCE, THEORY & METHODS | Algorithms | Studies | Graph theory | Graph coloring | Mathematical analysis | Upper bounds | Color | Graphs | Colouring | Automorphisms | Colour
Journal Article
Discrete Applied Mathematics, ISSN 0166-218X, 2010, Volume 158, Issue 4, pp. 261 - 276
We consider the problem of finding most balanced cuts among minimum s t -edge cuts and minimum s t -vertex cuts, for given vertices s and t , according to... 
Approximation algorithm | Balanced cut | Partially ordered knapsack | MATHEMATICS, APPLIED
Journal Article
SIAM journal on computing, ISSN 0097-5397, 04/2014, Volume 43, Issue 2, pp. 767 - 799
Journal Article
ISSN 1432-4350, 2017
Journal Article
Leibniz International Proceedings in Informatics, LIPIcs, ISSN 1868-8969, 2012, Volume 14, pp. 531 - 542
Conference Proceeding
Discrete Applied Mathematics, ISSN 0166-218X, 11/2017, Volume 231, p. 95
A rerouting sequence is a sequence of shortest st-paths such that consecutive paths differ in one vertex. We study the Shortest Path Rerouting Problem, which... 
Studies | Shortest-path problems | Routing | Graphs | Polynomials | Dynamic programming | Reconfiguration
Journal Article
SIAM Journal on Discrete Mathematics, ISSN 0895-4801, 2008, Volume 22, Issue 3, pp. 920 - 937
We present two lower bounds for the maximum number of leaves over all spanning trees of a graph. For connected, triangle-free graphs on n vertices, with... 
Max leaf | Extremal graph theory | Connected dominating set | Spanning tree | MATHEMATICS, APPLIED | extremal graph theory | APPROXIMATION | max leaf | connected dominating set | spanning tree
Journal Article
Journal of graph theory, ISSN 0364-9024, 2009, Volume 62, Issue 2, pp. 109 - 126
The Matching-Cut problem is the problem to decide whether a graph has an edge cut that is also a matching. Previously this problem was studied under the name... 
Matching-cut | decomposable graph | IR-72723 | Planar graph | Computational Complexity | matching‐cut | planar graph | computational complexity | Matching-Cut | Decomposable Graph | Computational complexity | MATHEMATICS | DECOMPOSABLE GRAPHS | CLIQUE-WIDTH | matching-cut | STABLE CUTSETS
Journal Article
Proceedings of the 14th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2014, ISSN 1611-3349, 07/2014, Volume 8503, pp. 86 - 97
We present a polynomial-time algorithm that, given two independent sets in a claw-free graph G, decides whether one can be transformed into the other by a... 
IR-93932 | METIS-309751 | Claw-free graph | EWI-25463 | Graph algorithms | Token Sliding | Reconfiguration
Conference Proceeding
SIAM Journal on Discrete Mathematics, ISSN 0895-4801, 2011, Volume 25, Issue 4, pp. 1652 - 1666
We consider the problem of finding a spanning tree that maximizes the number of leaves (MaxLeaf). We provide a 3/2-approximation algorithm for this problem... 
Maximum leaf | Connected dominating set | Approximation algorithm | Cubic graph | Spanning tree | MATHEMATICS, APPLIED | APPROXIMATION | DIRECTED TREES | maximum leaf | connected dominating set | spanning tree | approximation algorithm | cubic graph
Journal Article
Proceedings of the 9th International Symposium on Parameterized and Exact Computation, IPEC 2014, ISSN 1611-3349, 09/2014, Volume 8894, pp. 110 - 121
In the first part of this work we study the following question: Given two k-colorings α and β of a graph G on n vertices and an integer ℓ, can α be modified... 
Coloring | METIS-309750 | IR-93931 | EWI-25462 | Constraint satisfaction | Graph algorithms | Reconfiguration | Computational Complexity
Conference Proceeding
No results were found for your search.

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