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

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

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

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

We introduce in a general setting a dynamic programming method for solving reconfiguration problems. Our method is based on contracted solution graphs, which...

Computer Systems Organization and Communication Networks | Computer Science | Software Engineering/Programming and Operating Systems | Theory of Computation | Information Systems and Communication Service | Logics and Meanings of Programs | Data Structures and Information Theory | Algorithms | Coloring | Graphs | Polynomials | Dynamic programming | Reconfiguration

Computer Systems Organization and Communication Networks | Computer Science | Software Engineering/Programming and Operating Systems | Theory of Computation | Information Systems and Communication Service | Logics and Meanings of Programs | Data Structures and Information Theory | Algorithms | Coloring | Graphs | Polynomials | Dynamic programming | Reconfiguration

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

Maximum leaf | Minimum connected dominating set | APX-hard | Approximation algorithm | Cubic graph | Algorithms

Journal Article

6.
Full Text
Finding Paths between graph colourings: PSPACE-completeness and superpolynomial distances

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

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

We study the problem of finding a spanning tree with maximum number of leaves. We present a simple, linear time 2-approximation algorithm for this problem,...

Computer Systems Organization and Communication Networks | Data Structures, Cryptology and Information Theory | Algorithms | Approximation | Mathematics of Computing | Computer Science | Graphs | Theory of Computation | Algorithm Analysis and Problem Complexity | Algorithm | Optimization | COMPUTER SCIENCE, SOFTWARE ENGINEERING | MATHEMATICS, APPLIED | DIRECTED TREES | Computer science

Computer Systems Organization and Communication Networks | Data Structures, Cryptology and Information Theory | Algorithms | Approximation | Mathematics of Computing | Computer Science | Graphs | Theory of Computation | Algorithm Analysis and Problem Complexity | Algorithm | Optimization | COMPUTER SCIENCE, SOFTWARE ENGINEERING | MATHEMATICS, APPLIED | DIRECTED TREES | Computer science

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

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

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

In the unsplittable flow problem on a path, we are given a capacitated path $P$ and $n$ tasks, each task having a demand, a profit, and start and end vertices....

unsplittable flow | MSC-68R05 | EWI-25461 | IR-93936 | Resource Allocation | METIS-309749 | strong NP-hardness | constant-factor approximation | MSC-68W25 | maximum weight independent set | Maximum weight independent set | Strong NP-hardness | Unsplittable flow | Resource allocation | Constantfactor approximation | STORAGE | MATHEMATICS, APPLIED | constantfactor approximation | KNAPSACK-PROBLEM | resource allocation | RESOURCE-ALLOCATION | TREES | DISJOINT PATHS | COMPUTER SCIENCE, THEORY & METHODS | BANDWIDTH

unsplittable flow | MSC-68R05 | EWI-25461 | IR-93936 | Resource Allocation | METIS-309749 | strong NP-hardness | constant-factor approximation | MSC-68W25 | maximum weight independent set | Maximum weight independent set | Strong NP-hardness | Unsplittable flow | Resource allocation | Constantfactor approximation | STORAGE | MATHEMATICS, APPLIED | constantfactor approximation | KNAPSACK-PROBLEM | resource allocation | RESOURCE-ALLOCATION | TREES | DISJOINT PATHS | COMPUTER SCIENCE, THEORY & METHODS | BANDWIDTH

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

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

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

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

IR-93932 | METIS-309751 | Claw-free graph | EWI-25463 | Graph algorithms | Token Sliding | Reconfiguration

Conference Proceeding

19.
Full Text
A 3/2-approximation algorithm for finding spanning trees with many leaves in cubic graphs

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

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

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.